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

Disjoint NP-pairs are a well studied complexity theoretic concept with
important applications in cryptography and propositional proof
complexity.

In this paper we introduce a natural generalization of the notion of
disjoint NP-pairs to disjoint k-tuples of NP-sets for k>1.
We define subclasses of the class ... more >>>

We investigate the connection between optimal propositional
proof systems and complete languages for promise classes.
We prove that an optimal propositional proof system exists
if and only if there exists a propositional proof system
in which every promise class with the test set in co-NP
... more >>>

In this paper we investigate the following two questions:

Q1: Do there exist optimal proof systems for a given language L?
Q2: Do there exist complete problems for a given promise class C?

For concrete languages L (such as TAUT or SAT and concrete promise classes C (such as NP ... more >>>