All reports by Author Zenon Sadowski:

__
TR09-081
| 27th August 2009
__

Olaf Beyersdorff, Zenon Sadowski#### Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes

__
TR08-107
| 12th November 2008
__

Zenon Sadowski#### Optimal Proof Systems and Complete Languages

__
TR05-077
| 15th July 2005
__

Zenon Sadowski#### On a D-N-optimal acceptor for TAUT

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

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

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