Complexity class that is the set of languages expressible by first-order logic

69 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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.