ProbXiv
Explorersign in
Problem archiveProblem record

Statement

A generator is a map g:0,1∗→0,1∗g:{0,1}^*\rightarrow{0,1}^* whose restriction to inputs of length nn maps into strings of length m(n)>nm(n)>n and is computed by circuits of size polynomial in m(n)m(n). For a propositional proof system PP, let sP(φ){\bf s}_P(\varphi) denote the minimum length of a PP-proof of the tautology φ\varphi. A generator is hard for PP if, for every c≥1c\geq 1,

sP(τ(g)b)≤∣τ(g)b∣c≤∣b∣O(c)\bf s_P(\tau(g)_b)\leq |\tau(g)_b|^c\leq |b|^{O(c)}

holds for only finitely many bb, where τ(g)b\tau(g)_b expresses that bb is not in the range of the circuit defining gg. 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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.