1

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.

user2346
  • 631
  • 2
  • 7
  • 14

1 Answers1

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.

JSchlather
  • 15,427