Jan Krajicek

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 ... more >>>