ELEMENTARY - Descriptive Characterization

Descriptive Characterization

In descriptive complexity, ELEMENTARY is equal to the class of high order queries. This means that every language in the ELEMENTARY complexity class can be written as a high order formula that is true only for the elements on the language. More precisely, where indicates a tower of exponentiations and is the class of queries that begin with existential quantifiers of th order and then a formula of th order.

Read more about this topic:  ELEMENTARY