Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Proof System:
TR10-008 | 13th January 2010
Yijia Chen, Joerg Flum

On optimal proof systems and logics for PTIME

Revisions: 1

We prove that TAUT has a $p$-optimal proof system if and only if $L_\le$, a logic introduced in [Gurevich, 88], is a P-bounded logic for P. Furthermore, using the method developed in [Chen and Flum, 10], we show that TAUT has no \emph{effective} $p$-optimal proof system under some reasonable complexity-theoretic ... more >>>

TR17-056 | 7th April 2017
Paul Goldberg, Christos Papadimitriou

Towards a Unified Complexity Theory of Total Functions

Revisions: 1

The complexity class TFNP is the set of {\em total function} problems that belong to NP: every input has at least one output and outputs are easy to check for validity, but it may be hard to find an output. TFNP is not believed to have complete problems, but it ... more >>>

ISSN 1433-8092 | Imprint