Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-018 | 24th January 2004 00:00

Diagonalization in proof complexity

RSS-Feed




TR04-018
Authors: Jan Krajicek
Publication: 8th March 2004 13:26
Downloads: 3237
Keywords: 


Abstract:

We study the diagonalization in the context of proof
complexity. We prove that at least one of the
following three conjectures is true:

1. There is a boolean function computable in E
that has circuit complexity $2^{\Omega(n)}$.

2. NP is not closed under the complement.

3. There is no p-optimal propositional proof system.

We note that a variant of the statement seems to have
a bearing on the existence of good proof complexity generators.
In particular, we prove that if a minor variant
of a recent conjecture of Razborov is true (stating conditional
lower bounds for the Extended Frege proof system EF) then
actually unconditional lower bounds would follow for EF.



ISSN 1433-8092 | Imprint