The page on descriptive complexity theory in Wikipedia states the following:

"First-order logic defines the class FO, corresponding to AC0, the languages recognized by polynomial-size circuits of bounded depth, which equals the languages recognized by a concurrent random access machine in constant time."

How can we show that first order logic is equivalent to AC0?

In Clote and Kranakis' book Boolean Functions and Models of Computation (Springer, p. 34), it is states that symmetric boolean functions are in AC0.

Could we the state that symmetric functions are equivalent to AC0 and first order logic? I am guessing that no, but still...

  • 1
    $\begingroup$ Symmetric functions can be stronger than AC$^0$, for example MAJORITY is symmetric but not in AC$^0$. Conversely, a lot of functions in AC$^0$ aren't symmetric. $\endgroup$ – Yuval Filmus Jun 8 '14 at 15:04
  • 1
    $\begingroup$ For the equivalence of (DLOGTIME-uniform) AC$^0$ and FO, you can check Neil Immerman's book Descriptive Complexity. One direction should be easy. $\endgroup$ – Yuval Filmus Jun 8 '14 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.