1
$\begingroup$

PH is the complexity class that is the set of languages expressible by second-order logic. If so, is there any complexity class that is the set of languages expressible by first-order logic?

It seems likely that R is the complexity class that is the set of languages expressible by first-order logic, but I am not really sure.

  • 0
    @YuvalFilmus no.. and I got an answer! Thanks for help.2012-05-09

1 Answers 1

2

I'm just putting this here to remove it from the unanswered queue. From the wikipedia article on Descriptive Complexity Theory:

First-order logic defines the class FO, corresponding to $\mathsf{AC}^0$, the languages recognized by polynomial-size circuits of bounded depth, which equals the languages recognized by a concurrent random access machine in constant time.