Treffer: On optimal heuristic randomized semidecision procedures, with application to proof complexity

Title:
On optimal heuristic randomized semidecision procedures, with application to proof complexity
Authors:
Hirsch, Edward A., Itsykson, Dmitry
Contributors:
St. Petersburg Department of V.A. Steklov Mathematical Institute (PDMI RAS), Steklov Mathematical Institute [Moscow] (SMI | RAS), Russian Academy of Sciences [Moscow] (RAS)-Russian Academy of Sciences [Moscow] (RAS), Inria Nancy Grand Est & Loria, Jean-Yves Marion and Thomas Schwentick
Source:
27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010. :453-464
Publisher Information:
HAL CCSD, 2010.
Publication Year:
2010
Collection:
collection:STACS2010
Subject Terms:
propositional proof complexity, optimal algorithm, ACM: F.: Theory of Computation, F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, [INFO.INFO-CC]Computer Science [cs], Computational Complexity [cs.CC], [INFO.INFO-LO]Computer Science [cs], Logic in Computer Science [cs.LO]
Subject Geographic:
Nancy, France
Original Identifier:
HAL:
Document Type:
Konferenz conferenceObject<br />Conference papers
Language:
English
Access URL:
https://inria.hal.science/inria-00455819
https://inria.hal.science/inria-00455819/document
https://inria.hal.science/inria-00455819/file/hirsch.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00455819v1
Database:
HAL

Weitere Informationen

The existence of a (p-)optimal propositional proof system is a major open question in (proof) complexity; many people conjecture that such systems do not exist. Krajicek and Pudlak (1989) show that this question is equivalent to the existence of an algorithm that is optimal on all propositional tautologies. Monroe (2009) recently gave a conjecture implying that such algorithm does not exist. We show that in the presence of errors such optimal algorithms do exist. The concept is motivated by the notion of heuristic algorithms. Namely, we allow the algorithm to claim a small number of false "theorems" (according to any samplable distribution on non-tautologies) and err with bounded probability on other inputs. Our result can also be viewed as the existence of an optimal proof system in a class of proof systems obtained by generalizing automatizable proof systems.