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 a ∈ A, 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:
“Hesitation increases in relation to risk in equal proportion to age.”
—Ernest Hemingway (1899–1961)
“There is the falsely mystical view of art that assumes a kind of supernatural inspiration, a possession by universal forces unrelated to questions of power and privilege or the artist’s relation to bread and blood. In this view, the channel of art can only become clogged and misdirected by the artist’s concern with merely temporary and local disturbances. The song is higher than the struggle.”
—Adrienne Rich (b. 1929)
“In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (1871–1922)