Descriptive complexity theory (original) (raw)
Die deskriptive Komplexitätstheorie (beschreibende Komplexitätstheorie) ist ein Teilbereich der endlichen Modelltheorie, die den Zusammenhang der Ausdrucksstärke von Logiken und Komplexitätstheorie untersucht. Während Komplexitätsklassen wie NP oder PSPACE üblicherweise durch ein spezielles Maschinenmodell (üblicherweise Turingmaschinen) definiert werden, lassen sich mit Hilfe der deskriptiven Komplexitätstheorie diese Klassen auch durch „natürliche“ Logiken wie der Prädikatenlogik erster oder höherer Stufe oder Fixpunktlogiken charakterisieren.
| Property | Value |
|---|---|
| dbo: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) Die deskriptive Komplexitätstheorie (beschreibende Komplexitätstheorie) ist ein Teilbereich der endlichen Modelltheorie, die den Zusammenhang der Ausdrucksstärke von Logiken und Komplexitätstheorie untersucht. Während Komplexitätsklassen wie NP oder PSPACE üblicherweise durch ein spezielles Maschinenmodell (üblicherweise Turingmaschinen) definiert werden, lassen sich mit Hilfe der deskriptiven Komplexitätstheorie diese Klassen auch durch „natürliche“ Logiken wie der Prädikatenlogik erster oder höherer Stufe oder Fixpunktlogiken charakterisieren. (de) En informatique théorique, la complexité descriptive est une branche de la théorie de la complexité et de la théorie des modèles, qui caractérise les classes de complexité en termes de logique qui permet de décrire les problèmes. La complexité descriptive donne un nouveau point de vue car on définit des classes de complexité sans faire appel à une notion de machines comme les machines de Turing. Par exemple la classe NP correspond à l'ensemble des problèmes exprimables en logique du second ordre existentielle : c'est le théorème de Fagin. (fr) 記述計算量（きじゅつけいさんりょう、英: Descriptive complexity）は、有限モデル理論の一種であり、計算複雑性理論と数理論理学の一分野である。複雑性クラスを言語で表現するのに必要とされる論理の種類によって特徴付けることを目的とする。例えば、PHは二階述語論理の論理式で表現される言語のクラスと正確に対応している。このような複雑性と論理の繋がりによって、2つの分野の間で容易に変換が可能となり、新たな証明手法を生み出したり、ある複雑性クラスが本質的なものであって、特定の抽象機械に結びつくものではないことを示すことができる。 (ja) |
| dbo:wikiPageExternalLink | http://www.cs.umass.edu/~immerman/descriptive_complexity.html http://worldcat.org/oclc/901297152%7Ctitle=Descriptive |
| dbo:wikiPageID | 1212009 (xsd:integer) |
| dbo:wikiPageLength | 18396 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1097139985 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:FO_(complexity) dbr:NP_(complexity) dbr:HO_(complexity) dbc:Finite_model_theory dbr:Star-free_language dbr:Oracle_machine dbr:Co-NP dbr:Moshe_Vardi dbr:NL_(complexity) dbr:LH_(complexity) dbr:L_(complexity) dbr:Logic dbr:Complexity_class dbr:Computational_complexity_theory dbr:Computational_problem dbr:Horn_clause dbr:PH_(complexity) dbr:P_(complexity) dbr:Time_complexity dbr:Transitive_closure dbr:Tuple dbr:Least_fixed_point dbr:ELEMENTARY dbr:EXPTIME dbr:First-order_logic dbr:PSPACE dbr:Query_(complexity) dbr:Tetration dbr:AC0 dbr:AC_(complexity) dbc:Computational_complexity_theory dbr:Abstract_machine dbr:Higher-order_logic dbr:Disjunctive_normal_form dbr:Domain_of_discourse dbc:Descriptive_complexity dbr:Polynomial_hierarchy dbr:Circuit_complexity dbr:Iff dbr:Second-order_logic dbr:Neil_Immerman dbr:SO_(complexity) dbr:Fagin's_theorem dbr:Finite_model_theory dbr:Fixed-point_logic dbr:NTIME dbr:Partial_fixed-point_logic dbr:Least_fixed-point_logic dbr:Ronald_Fagin dbr:Krom_formula dbr:Transitive_closure_logic dbr:PTIME dbr:Logical_system dbr:Concurrent_random_access_machine dbr:Abiteboul-Vianu_Theorem |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Mvar dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Finite_model_theory dbc:Computational_complexity_theory dbc:Descriptive_complexity |
| rdfs:comment | Die deskriptive Komplexitätstheorie (beschreibende Komplexitätstheorie) ist ein Teilbereich der endlichen Modelltheorie, die den Zusammenhang der Ausdrucksstärke von Logiken und Komplexitätstheorie untersucht. Während Komplexitätsklassen wie NP oder PSPACE üblicherweise durch ein spezielles Maschinenmodell (üblicherweise Turingmaschinen) definiert werden, lassen sich mit Hilfe der deskriptiven Komplexitätstheorie diese Klassen auch durch „natürliche“ Logiken wie der Prädikatenlogik erster oder höherer Stufe oder Fixpunktlogiken charakterisieren. (de) En informatique théorique, la complexité descriptive est une branche de la théorie de la complexité et de la théorie des modèles, qui caractérise les classes de complexité en termes de logique qui permet de décrire les problèmes. La complexité descriptive donne un nouveau point de vue car on définit des classes de complexité sans faire appel à une notion de machines comme les machines de Turing. Par exemple la classe NP correspond à l'ensemble des problèmes exprimables en logique du second ordre existentielle : c'est le théorème de Fagin. (fr) 記述計算量（きじゅつけいさんりょう、英: Descriptive complexity）は、有限モデル理論の一種であり、計算複雑性理論と数理論理学の一分野である。複雑性クラスを言語で表現するのに必要とされる論理の種類によって特徴付けることを目的とする。例えば、PHは二階述語論理の論理式で表現される言語のクラスと正確に対応している。このような複雑性と論理の繋がりによって、2つの分野の間で容易に変換が可能となり、新たな証明手法を生み出したり、ある複雑性クラスが本質的なものであって、特定の抽象機械に結びつくものではないことを示すことができる。 (ja) 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) |
| rdfs:label | Deskriptive Komplexitätstheorie (de) Descriptive complexity theory (en) Complexité descriptive (fr) 記述計算量 (ja) |
| owl:sameAs | freebase:Descriptive complexity theory wikidata:Descriptive complexity theory dbpedia-de:Descriptive complexity theory dbpedia-fr:Descriptive complexity theory dbpedia-ja:Descriptive complexity theory https://global.dbpedia.org/id/EZmh |
| prov:wasDerivedFrom | wikipedia-en:Descriptive_complexity_theory?oldid=1097139985&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Descriptive_complexity_theory |
| is dbo:wikiPageRedirects of | dbr:FO_(complexity) dbr:HO_(complexity) dbr:FO(PFP) dbr:SO_(complexity) dbr:Descriptional_complexity dbr:Descriptive_complexity dbr:Immerman-Vardi dbr:Immerman-Vardi_theorem |
| is dbo:wikiPageWikiLink of | dbr:FO_(complexity) dbr:Model_theory dbr:NP_(complexity) dbr:HO_(complexity) dbr:Descriptive_Complexity dbr:List_of_mathematical_logic_topics dbr:Mathematical_logic dbr:Martin_Grohe dbr:MAXEkSAT dbr:Complexity_and_Real_Computation dbr:Computational_complexity_theory dbr:Fixed_point_(mathematics) dbr:Fragment_(logic) dbr:Kolmogorov_complexity dbr:FO(PFP) dbr:Monadic_second-order_logic dbr:SO_(complexity) dbr:Fixed-point_logic dbr:Descriptional_complexity dbr:Descriptive_complexity dbr:Immerman-Vardi dbr:Immerman-Vardi_theorem |
| is foaf:primaryTopic of | wikipedia-en:Descriptive_complexity_theory |