Hard generator conjecture for propositional proof systems
Statement
A generator is a map whose restriction to inputs of length maps into strings of length and is computed by circuits of size polynomial in . For a propositional proof system , let denote the minimum length of a -proof of the tautology . A generator is hard for if, for every ,
holds for only finitely many , where expresses that is not in the range of the circuit defining . Hard generator conjecture. There exists a generator hard for all propositional proof systems; equivalently, its range intersects every infinite nondeterministic polynomial-time set. In fact, such a generator exists that is computable in polynomial time. This hypothesis is used in proof complexity to obtain generators whose range avoids efficiently recognizable hard sets, and its relationship with proof-system simulations is a central theme of the paper.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.