2026-07-21T23:54:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2475 2024-03-06T10:33:25Z ddc:004 open_access

On Optimal Heuristic Randomized Semidecision Procedures, with Application to Proof Complexity Hirsch, Edward A. Itsykson, Dmitry Propositional proof complexity optimal algorithm 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. Kraj\'{\i}\v{c}ek and Pudl\'{a}k \cite{KP} show that this question is equivalent to the existence of an algorithm that is optimal\footnote{Recent papers \cite{Monroe} call such algorithms \emph{$p$-optimal} while traditionally Levin's algorithm was called \emph{optimal}. We follow the older tradition. Also there is some mess in terminology here, thus please see formal definitions in Sect.~\ref{sec:prelim} below.} on all propositional tautologies. Monroe \cite{Monroe} recently gave a conjecture implying that such algorithm does not exist. We show that in the presence of errors such optimal algorithms \emph{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 polynomial-time 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Edward A. Hirsch and Dmitry Itsykson 2010 Is Part Of LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2010.2475 urn:nbn:de:0030-drops-24753 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2475 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode