About: Descriptive complexity theory

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Descriptive complexity theory Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : el.dbpedia.org associated with source document(s)

Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them. For example, PH, the union of all complexity classes in the polynomial hierarchy, is precisely the class of languages expressible by statements of second-order logic. This connection between complexity and the logic of finite structures allows results to be transferred easily from one area to the other, facilitating new proof methods and providing additional evidence that the main complexity classes are somehow "natural" and not tied to the specific abstract machines used to define them.

Attributes	Values
rdfs:label	Descriptive complexity theory (en)
rdfs:comment	Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them. For example, PH, the union of all complexity classes in the polynomial hierarchy, is precisely the class of languages expressible by statements of second-order logic. This connection between complexity and the logic of finite structures allows results to be transferred easily from one area to the other, facilitating new proof methods and providing additional evidence that the main complexity classes are somehow "natural" and not tied to the specific abstract machines used to define them. (en)
sameAs	Descriptive complexity theory
dbp:wikiPageUsesTemplate	dbt:Cite_book dbt:Mvar dbt:Reflist
Subject	Computational complexity theory Descriptive complexity Finite model theory
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Descriptive_complexity_theory?oldid=1074105079&ns=0
Wikipage page ID	1212009 (xsd:integer)
page length (characters) of wiki page	18345 (xsd:nonNegativeInteger)
Wikipage revision ID	1074105079 (xsd:integer)
Link from a Wikipage to another Wikipage	Formal system Logic NL (complexity) NP-completeness NTIME Ronald Fagin 2-satisfiability AC0 AC (complexity) Abstract machine Tuple Computational complexity theory Descriptive complexity Finite model theory Disjunctive normal form Domain of discourse PH (complexity) PSPACE P (complexity) Second-order logic Circuit complexity Horn clause Time complexity Co-NP Complexity class Algorithmic complexity Computational problem ELEMENTARY EXPTIME Higher-order logic Moshe Vardi Oracle machine Parallel RAM Finite model theory First-order logic Fixed-point logic If and only if Descriptive complexity theory Fagin's theorem LH (complexity) L (complexity) Tetration Transitive closure Star-free language Least fixed point Neil Immerman Polynomial hierarchy Query (complexity) dbr:Abiteboul-Vianu_Theorem
has abstract	Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them. For example, PH, the union of all complexity classes in the polynomial hierarchy, is precisely the class of languages expressible by statements of second-order logic. This connection between complexity and the logic of finite structures allows results to be transferred easily from one area to the other, facilitating new proof methods and providing additional evidence that the main complexity classes are somehow "natural" and not tied to the specific abstract machines used to define them. Specifically, each logical system produces a set of queries expressible in it. The queries – when restricted to finite structures – correspond to the computational problems of traditional complexity theory. The first main result of descriptive complexity was Fagin's theorem, shown by Ronald Fagin in 1974. It established that NP is precisely the set of languages expressible by sentences of existential second-order logic; that is, second order logic excluding universal quantification over relations, functions, and subsets. Many other classes were later characterized in such a manner. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Descriptive_complexity_theory
is Wikipage redirect of	SO (complexity) FO(PFP) FO (complexity) HO (complexity) Descriptional complexity Descriptive complexity Immerman-Vardi Immerman-Vardi theorem
is Link from a Wikipage to another Wikipage of	Fragment (logic) Logic of graphs NP-completeness AC0 BIT predicate Juhani Karhumäki History of logic List of mathematical logic topics Complexity and Real Computation Algorithmic complexity ELEMENTARY Finite model theory First-order reduction Fixed-point logic Immerman–Szelepcsényi theorem FO(PFP) Descriptional Complexity of Formal Systems Descriptive Complexity Descriptive complexity theory FO FO (complexity) Fagin's theorem HO (complexity) LH (complexity) L (complexity) Model theory Monadic second-order logic Kolmogorov complexity

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (72 GB total memory, 1 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software