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

Olaf Beyersdorff

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

Zenon Sadowski

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

Olaf Beyersdorff, Zenon Sadowski

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

Leroy Chew

Quantified Boolean Formulas (QBFs) extend propositional formulas with Boolean quantifiers. Working with QBF differs from propositional logic in its quantifier handling, but as propositional satisfiability (SAT) is a subproblem of QBF, all SAT hardness in solving and proof complexity transfers to QBF. This makes it difficult to analyse efforts dealing ... more >>>

Hunter Monroe

If no optimal propositional proof system exists, we (and independently Pudlák) prove that ruling out length $t$ proofs of any unprovable sentence is hard. This mapping from unprovable to hard-to-prove sentences powerfully translates facts about noncomputability into complexity theory. For instance, because proving string $x$ is Kolmogorov random ($x{\in}R$) is ... more >>>