Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Descriptive_complexity_theory> ?p ?o. }
Showing items 1 to 24 of
24
with 100 items per page.
- Descriptive_complexity_theory 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, most of them by Neil Immerman: 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. First-order logic with a commutative, transitive closure operator added yields SL, which equals L, problems solvable in logarithmic space. First-order logic with a transitive closure operator yields NL, the problems solvable in nondeterministic logarithmic space. In the presence of linear order, first-order logic with a least fixed point operator gives P, the problems solvable in deterministic polynomial time. Existential second-order logic yields NP, as mentioned above. Universal second-order logic (excluding existential second-order quantification) yields co-NP. Second-order logic corresponds to PH. Second-order logic with a transitive closure (commutative or not) yields PSPACE, the problems solvable in polynomial space. Second-order logic with a least fixed point operator gives EXPTIME, the problems solvable in exponential time. HO, logic with existential quantifier of order followed by a formula of order is equal to NTIME HO=NTIME( HO is equal to ELEMENTARY↑".
- Descriptive_complexity_theory wikiPageExternalLink genspec.pdf.
- Descriptive_complexity_theory wikiPageExternalLink tcs93.pdf.
- Descriptive_complexity_theory wikiPageExternalLink descriptive_complexity.html.
- Descriptive_complexity_theory wikiPageExternalLink capture.pdf.
- Descriptive_complexity_theory wikiPageID "1212009".
- Descriptive_complexity_theory wikiPageRevisionID "585802136".
- Descriptive_complexity_theory hasPhotoCollection Descriptive_complexity_theory.
- Descriptive_complexity_theory subject Category:Computational_complexity_theory.
- Descriptive_complexity_theory subject Category:Descriptive_complexity.
- Descriptive_complexity_theory subject Category:Finite_model_theory.
- Descriptive_complexity_theory 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.".
- Descriptive_complexity_theory label "Complexité descriptive".
- Descriptive_complexity_theory label "Descriptive complexity theory".
- Descriptive_complexity_theory label "Deskriptive Komplexitätstheorie".
- Descriptive_complexity_theory label "記述計算量".
- Descriptive_complexity_theory sameAs Deskriptive_Komplexitätstheorie.
- Descriptive_complexity_theory sameAs Complexité_descriptive.
- Descriptive_complexity_theory sameAs 記述計算量.
- Descriptive_complexity_theory sameAs m.04hqc8.
- Descriptive_complexity_theory sameAs Q1200755.
- Descriptive_complexity_theory sameAs Q1200755.
- Descriptive_complexity_theory wasDerivedFrom Descriptive_complexity_theory?oldid=585802136.
- Descriptive_complexity_theory isPrimaryTopicOf Descriptive_complexity_theory.