Back to Search
Start Over
Optimal Proof Systems, Optimal Acceptors and Recursive Presentability.
- Source :
- Fundamenta Informaticae; 2007, Vol. 79 Issue 1-2, p169-185, 17p
- Publication Year :
- 2007
-
Abstract
- We advocate the thesis that the following general statements are equivalent: the existence of an optimal proof system, the existence of an optimal acceptor (an algorithm with optimality property stated only for input strings which are accepted), and the existence of a suitable recursive presentation of the class of all easy (polynomial-time recognizable) subsets of TAUT (SAT). We prove three concrete versions of this thesis with different variants of notions appearing in it. These versions give alternative characterizations of the following problems: the existence of a p-optimal proof system for SAT, the existence of an optimal proof system for TAUT, and the existence of an optimal and automatizable proof system for TAUT. [ABSTRACT FROM AUTHOR]
- Subjects :
- ALGORITHMS
ALGEBRA
POLYNOMIALS
APPROXIMATION theory
MATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 01692968
- Volume :
- 79
- Issue :
- 1-2
- Database :
- Complementary Index
- Journal :
- Fundamenta Informaticae
- Publication Type :
- Academic Journal
- Accession number :
- 26554502