[FOM] complexity of P-timeness

[leivant]

>> rpax0 at seznam.cz wrote:
>>> what is the complexity (in the arithmetical hierarchy) of Godel 
>>> numbers of Turing machines
>>> that run in time O(n^k) for a fixed k>0?
Mitchell Spector wrote:
>> The following is a partial solution to Jan's question, if I'm not 
>> mistaken in some part of the proof:
...
>> I would imagine that this is likely already known.  I'd appreciate 
>> hearing of any reference.

For PTime (without the fixed degree) see:

Petr Hajek:
Arithmetical Hierarchy and Complexity of Computation.
TCS 1979, pages 227-237.
Theorem 2, page 230.

A variant of that proof should work for fixed exponents as well.

best wishes and happy new year  - daniel

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20111231/84c77ade/attachment.html>