On Optimal Heuristic Randomized Semidecision Procedures, with Applications to Proof Complexity and Cryptography

Edward A. Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal

Research output

3 Citations (Scopus)

Abstract

The existence of an optimal propositional proof system is a major open question in proof complexity; many people conjecture that such systems do not exist. Krajíček and Pudlák (J. Symbol. Logic 54(3):1063, 1989) show that this question is equivalent to the existence of an algorithm that is optimal on all propositional tautologies. Monroe (Theor. Comput. Sci. 412(4-5):478, 2011) recently presented a conjecture implying that such an algorithm does not exist. We show that if one allows errors, then such optimal algorithms do exist. The concept is motivated by the notion of heuristic algorithms. Namely, we allow an algorithm, called a heuristic acceptor, to claim a small number of false "Theorems" and err with bounded probability on other inputs. The amount of false "Theorems" is measured according to a polynomial-time samplable distribution on non-tautologies. Our result remains valid for all recursively enumerable languages and can also be viewed as the existence of an optimal weakly automatizable heuristic proof system. The notion of a heuristic acceptor extends the notion of a classical acceptor; in particular, an optimal heuristic acceptor for any distribution simulates every classical acceptor for the same language. We also note that the existence of a co-NP-language L with a polynomial-time samplable distribution on L̄ that has no polynomial-time heuristic acceptors is equivalent to the existence of an infinitely-often one-way function.

Original languageEnglish
Pages (from-to)179-195
Number of pages17
JournalTheory of Computing Systems
Volume51
Issue number2
DOIs
Publication statusPublished - 1 Aug 2012

Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'On Optimal Heuristic Randomized Semidecision Procedures, with Applications to Proof Complexity and Cryptography'. Together they form a unique fingerprint.

  • Cite this