Descriptive complexity theory
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.
Wikipage redirect
AC0BIT predicateComplexity and Real ComputationComputational complexity theoryDescriptional Complexity of Formal SystemsDescriptional complexityDescriptive ComplexityDescriptive complexityELEMENTARYFO (complexity)Fagin's theoremFinite model theoryFragment (logic)HO (complexity)History of logicImmerman–Szelepcsényi theoremJuhani KarhumäkiKolmogorov complexityLeast fixed pointList of mathematical logic topicsLogic of graphsMartin GroheMathematical logicModel theoryMonadic second-order logicNP (complexity)Neil ImmermanPH (complexity)PSPACEP (complexity)P versus NP problemQuery (complexity)SO (complexity)Second-order logicSpectrum of a sentence
Link from a Wikipage to another Wikipage
primaryTopic
Descriptive complexity theory
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.
has abstract
En informatique théorique, la ...... : c'est le théorème de Fagin.
@fr
記述計算量(きじゅつけいさんりょう、英: Descripti ...... 特定の抽象機械に結びつくものではないことを示すことができる。
@ja
Link from a Wikipage to an external page
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
958,326,436
Link from a Wikipage to another Wikipage
wikiPageUsesTemplate
comment
En informatique théorique, la ...... : c'est le théorème de Fagin.
@fr
記述計算量(きじゅつけいさんりょう、英: Descripti ...... 特定の抽象機械に結びつくものではないことを示すことができる。
@ja
label
Complexité descriptive
@fr
Descriptive complexity theory
@en
Deskriptive Komplexitätstheorie
@de
記述計算量
@ja