Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR08-083 | 10th June 2008 00:00

A logic for PTIME and a parameterized halting problem


Authors: Yijia Chen, Jörg Flum
Publication: 17th September 2008 08:51
Downloads: 3936


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 Turing machines has been given in [Nash, Remmel, and Vianu, 05]. We analyze the precise relationship between L_Y and p-Acc. Moreover, we show that p-Acc is not fixed-parameter tractable if ``P \ne NP holds for all time constructible functions.'' This property also implies that the natural parameterization of Goedel's proof predicate is not fixed-parameter tractable. Furthermore, the complexity of various variants of p-Acc is considered.

ISSN 1433-8092 | Imprint