Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PROOF SYSTEM:
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

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

TR20-073 | 5th May 2020
Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov

#### Lower Bounds on OBDD Proofs with Several Orders

This paper is motivated by seeking lower bounds on OBDD($\land$, weakening, reordering) refutations, namely OBDD refutations that allow weakening and arbitrary reorderings. We first work with 1-NBP($\land$) refutations based on read-once nondeterministic branching programs. These generalize OBDD($\land$, reordering) refutations. There are polynomial size 1-NBP($\land$) refutations of the pigeonhole principle, hence ... more >>>

ISSN 1433-8092 | Imprint