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