ECCC-Report TR08-083https://eccc.weizmann.ac.il/report/2008/083Comments and Revisions published for TR08-083en-usWed, 17 Sep 2008 08:51:51 +0300
Paper TR08-083
| A logic for PTIME and a parameterized halting problem |
Yijia Chen,
Jörg Flum
https://eccc.weizmann.ac.il/report/2008/083In [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.
Wed, 17 Sep 2008 08:51:51 +0300https://eccc.weizmann.ac.il/report/2008/083