Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR10-008 | 8th April 2010 10:26

On optimal proof systems and logics for PTIME

RSS-Feed




Revision #1
Authors: Yijia Chen, Joerg Flum
Accepted on: 8th April 2010 10:26
Downloads: 1284
Keywords: 


Abstract:

We prove that TAUT has a $p$-optimal proof system if and only if a logic related to least fixed-point logic captures polynomial time on all finite structures. Furthermore, we show that TAUT has no {\em effective} $p$-optimal proof system if $\textup{NTIME}(h^{O(1)}) \not\subseteq \textup{DTIME}(h^{O(\log h)})$ for every time constructible and increasing function $h$.



Changes to previous version:

Minor corrections.


Paper:

TR10-008 | 13th January 2010 08:20

On optimal proof systems and logics for PTIME





TR10-008
Authors: Yijia Chen, Joerg Flum
Publication: 15th January 2010 18:18
Downloads: 1673
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint