On the computational complexity of finding hard tautologies

's. We consider two more general search problems involving finding a hard formula, {�f Cert} and {�f Find}, motivated by two hypothetical situations: that one can prove that

p e q c o p

and that no optimal proof system exists. In {�f Cert} one is asked to find a witness that a given non-deterministic circuit with

k

inputs does not define

T A U T c a p k k

. In {�f Find}, given

1^{(k)}

and a tautology

a l p h a

of size at most

k^{c_{0}}

, one should output a size

k

tautology

that has no size

k^{c_{1}}

P

-proof from substitution instances of

a l p h a

. We shall prove, assuming the existence of an exponentially hard one-way permutation, that {�f Cert} cannot be solved by a time

2^{O (k)}

algorithm. Using a stronger hypothesis about the proof complexity of Nisan-Wigderson generator we show that both problems {�f Cert} and {�f Find} are actually only partially defined for infinitely many

k

(i.e. there are inputs corresponding to

k

for which the problem has no solution). The results are based on interpreting the Nisan-Wigderson generator as a proof system.

Recommendations

Cited in

(7)

This page was built for publication: On the computational complexity of finding hard tautologies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5402611)