Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: disjoint NP-pairs

Sortuj według:

Ogranicz wyniki do:

Optimal Proof Systems, Optimal Acceptors and Recursive Presentability

Sadowski Z.

Fundamenta Informaticae

2007

Vol. 79, nr 1-2

169-185

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.