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.