Unit:
Κατεύθυνση Μαθηματική ΛογικήLibrary of the School of Science
Author:
Papamakarios Theodoros
Supervisors info:
Στάθης Ζάχος, Καθηγητής
Σταύρος Κοσμαδάκης, Καθηγητής
Original Title:
Proof Complexity: A Tableau Perspective
Translated title:
Proof Complexity: A Tableau Perspective
Summary:
The method of semantic tableaux (or simply tableaux) is arguably
one of the most elegant proof systems. Unfortunately, it hasn’t received
much attention in the proof complexity literature, mainly due to early
negative results, concerning the complexity of cut-free tableaux. We bring tableaux to the fore, introducing the
measures of tableau depth and width. Equipped with these, we show in
an elegant, uniform way several known results spanning proof complexity,
from a tableau viewpoint.
Main subject category:
Science
Keywords:
proof complexity, tableaux, width, depth, consistency property
