Second-order Logic - Relation To Computational Complexity

Relation To Computational Complexity

The expressive power of various forms of second-order logic on finite structures is intimately tied to computational complexity theory. The field of descriptive complexity studies which computational complexity classes can be characterized by the power of the logic needed to express languages (sets of finite strings) in them. A string w = w1···wn in a finite alphabet A can be represented by a finite structure with domain D = {1,...,n}, unary predicates Pa for each aA, satisfied by those indices i such that wi = a, and additional predicates which serve to uniquely identify which index is which (typically, one takes the graph of the successor function on D or the order relation <, possibly with other arithmetic predicates). Conversely, the table of any finite structure can be encoded by a finite string.

With this identification, we have the following characterizations of variants of second-order logic over finite structures:

  • REG (the set of regular languages) is definable by monadic, second-order formulas (Büchi's theorem, 1960)
  • NP is the set of languages definable by existential, second-order formulas (Fagin's theorem, 1974).
  • co-NP is the set of languages definable by universal, second-order formulas.
  • PH is the set of languages definable by second-order formulas.
  • PSPACE is the set of languages definable by second-order formulas with an added transitive closure operator.
  • EXPTIME is the set of languages definable by second-order formulas with an added least fixed point operator.

Relationships among these classes directly impact the relative expressiveness of the logics over finite structures; for example, if PH = PSPACE, then adding a transitive closure operator to second-order logic would not make it any more expressive over finite structures.

Read more about this topic:  Second-order Logic

Famous quotes containing the words relation to, relation and/or complexity:

    ... a worker was seldom so much annoyed by what he got as by what he got in relation to his fellow workers.
    Mary Barnett Gilson (1877–?)

    Concord is just as idiotic as ever in relation to the spirits and their knockings. Most people here believe in a spiritual world ... in spirits which the very bullfrogs in our meadows would blackball. Their evil genius is seeing how low it can degrade them. The hooting of owls, the croaking of frogs, is celestial wisdom in comparison.
    Henry David Thoreau (1817–1862)

    The price we pay for the complexity of life is too high. When you think of all the effort you have to put in—telephonic, technological and relational—to alter even the slightest bit of behaviour in this strange world we call social life, you are left pining for the straightforwardness of primitive peoples and their physical work.
    Jean Baudrillard (b. 1929)