Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR08-107 | 12th November 2008
Zenon Sadowski

Optimal Proof Systems and Complete Languages

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

TR05-077 | 15th July 2005
Zenon Sadowski

On a D-N-optimal acceptor for TAUT

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

ISSN 1433-8092 | Imprint