Miklos Ajtai

Suppose that $p$ is a prime number $A$ is a finite set

with $n$ elements

and for each sequence $a=<a_{1},...,a_{k}>$ of length $k$ from the

elements of

$A$, $x_{a}$ is a variable. (We may think that $k$ and $p$ are fixed an

$n$ is sufficiently large.) We will ...
more >>>

Jochen Me\3ner, Jacobo Toran

A polynomial time computable function $h:\Sigma^*\to\Sigma^*$ whose range

is the set of tautologies in Propositional Logic (TAUT), is called

a proof system. Cook and Reckhow defined this concept

and in order to compare the relative strenth of different proof systems,

they considered the notion ...
more >>>

Shai Ben-David, Anna Gringauze.

We investigate sufficient conditions for the existence of

optimal propositional proof systems (PPS).

We concentrate on conditions of the form CoNF = NF.

We introduce a purely combinatorial property of complexity classes

- the notions of {\em slim} vs. {\em fat} classes.

These notions partition the ...
more >>>

Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang

We study the question of whether the class DisNP of

disjoint pairs (A, B) of NP-sets contains a complete pair.

The question relates to the question of whether optimal

proof systems exist, and we relate it to the previously

studied question of whether there exists ...
more >>>

Olaf Beyersdorff

We investigate the class of disjoint NP-pairs under different reductions.

The structure of this class is intimately linked to the simulation order

of propositional proof systems, and we make use of the relationship between

propositional proof systems and theories of bounded arithmetic as the main

tool of our analysis.

more >>>

Christian Glaßer, Alan L. Selman, Liyu Zhang

We prove that every disjoint NP-pair is polynomial-time, many-one equivalent to

the canonical disjoint NP-pair of some propositional proof system. Therefore, the degree structure of the class of disjoint NP-pairs and of all canonical pairs is

identical. Secondly, we show that this degree structure is not superficial: Assuming there exist ...
more >>>

Zenon Sadowski

The notion of an optimal acceptor for TAUT (the optimality

property is stated only for input strings from TAUT) comes from the line

of research aimed at resolving the question of whether optimal

propositional proof systems exist. In this paper we introduce two new

types of optimal acceptors, a D-N-optimal ...
more >>>

Olaf Beyersdorff

For a proof system P we introduce the complexity class DNPP(P)

of all disjoint NP-pairs for which the disjointness of the pair is

efficiently provable in the proof system P.

We exhibit structural properties of proof systems which make the

previously defined canonical NP-pairs of these proof systems hard ...
more >>>

Olaf Beyersdorff

In this paper we ask the question whether the extended Frege proof

system EF satisfies a weak version of the deduction theorem. We

prove that if this is the case, then complete disjoint NP-pairs

exist. On the other hand, if EF is an optimal proof system, ...
more >>>

Christian Glaßer, Alan L. Selman, Liyu Zhang

We investigate the connection between propositional proof systems and their canonical pairs. It is known that simulations between proof systems translate to reductions between their canonical pairs. We focus on the opposite direction and study the following questions.

Q1: Where does the implication [can(f) \le_m can(g) => f \le_s ... more >>>

Olaf Beyersdorff, Johannes Köbler, Sebastian Müller

One of the starting points of propositional proof complexity is the seminal paper by Cook and Reckhow (JSL 79), where they defined

propositional proof systems as poly-time computable functions which have all propositional tautologies as their range. Motivated by provability consequences in bounded arithmetic, Cook and Krajicek (JSL 07) have ...
more >>>