ECCC-Report TR22-120https://eccc.weizmann.ac.il/report/2022/120Comments and Revisions published for TR22-120en-usThu, 25 Aug 2022 10:58:29 +0300
Comment 1
| A formulation |
Jan Krajicek
https://eccc.weizmann.ac.il/report/2022/120#comment1The condition in the conjecture is supposed to mean:
|g(x)| = 1 + |x|.Thu, 25 Aug 2022 10:58:29 +0300https://eccc.weizmann.ac.il/report/2022/120#comment1
Paper TR22-120
| On the existence of strong proof complexity generators |
Jan Krajicek
https://eccc.weizmann.ac.il/report/2022/120The working conjecture from K'04 that there is a proof complexity generator hard for all
proof systems can be equivalently formulated (for p-time generators) without a reference to proof complexity notions
as follows:
\begin{itemize}
\item There exist a p-time function $g$ extending each input by one bit such that its range $rng(g)$
intersects all infinite NP sets.
\end{itemize}
We consider several facets of this conjecture, including its links to bounded arithmetic (witnessing and
independence results) and the range avoidance problem,
to time-bounded Kolmogorov complexity, to feasible disjunction property of propositional proof
systems and to complexity of proof search.
We argue that a specific gadget generator from K'08 is a good candidate for $g$.Wed, 24 Aug 2022 14:01:20 +0300https://eccc.weizmann.ac.il/report/2022/120