Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PROOF COMPLEXITY GENERATORS:
Reports tagged with proof complexity generators:
TR04-018 | 24th January 2004
Jan Krajicek

#### Diagonalization in proof complexity

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

TR22-120 | 24th August 2022
Jan Krajicek

#### On the existence of strong proof complexity generators

\item There exist a p-time function $g$ extending each input by one bit such that its ... more >>>