Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Logic for PTIME:
TR08-083 | 10th June 2008
Yijia Chen, Jörg Flum

A logic for PTIME and a parameterized halting problem

In [Blass, Gurevich, and Shelah, 99] a logic L_Y has been introduced as a possible candidate for a logic capturing the PTIME properties of structures (even in the absence of an ordering of their universe). A reformulation of this problem in terms of a parameterized halting problem p-Acc for nondeterministic ... more >>>

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

ISSN 1433-8092 | Imprint