Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The standard complexity classes such as P, NP are usually defined using Turing Machines. In finite model theory those classes can be defined via the classical first-order/second-order logics.

I am curious whether there exists an equivalent definition of such classes via $\mu$-recursive functions. What about register machines? lambda calculus? etc? In computability theory it is known that $\mu$-recursive functions, counter machines, lambda calculus and Turing Machines are all equivalent. (https://en.wikipedia.org/wiki/Computable_function)

share|improve this question
    
You can define PTIME using first-order logic? FO characterises LOGSPACE. For PTIME there is no such characterisation, only LFP on ordered structures. –  The User Jul 16 '13 at 9:00
    
You are absolutely right. Actually I have in mind in general finite model theory characterises complexity classes via FO/MSO/Fixed-point. I don't don't really mean P,NP. Thank you for your answer though. –  Tony Tan Jul 16 '13 at 9:33
    
I mean, actually it is unknown whether there is such a characterisation for PTIME, thus you would be famous if you could. ;) And I am sorry, FO is weaker than LOGSPACE, that was my point. –  The User Jul 16 '13 at 9:38
    
It is true. Thanks anyway for the answer... :-) –  Tony Tan Jul 16 '13 at 10:03
add comment

1 Answer

up vote 4 down vote accepted

Yes, there is. See [Cob64]. The idea is to replace primitive recursion in the definition of primitive recursive functions with bounded recursion on notion.

Another more delicate approach is taken in [BC92].

share|improve this answer
    
Thank you very much. –  Tony Tan Jul 16 '13 at 9:30
    
@Tony, you are welcome. –  Kaveh Jul 16 '13 at 9:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.