Fagin's theorem is the oldest result of descriptive complexity theory, a branch of computational complexity theory that characterizes complexity classes in terms of logic-based descriptions of their problems rather than by the behavior of algorithms for solving those problems.The theorem states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Satz von Fagin (de)
- Fagin's theorem (en)
- Théorème de Fagin (fr)
- Teorema de Fagin (pt)
|
| rdfs:comment
| - Fagin's theorem is the oldest result of descriptive complexity theory, a branch of computational complexity theory that characterizes complexity classes in terms of logic-based descriptions of their problems rather than by the behavior of algorithms for solving those problems.The theorem states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP. (en)
- Der Satz von Fagin ist ein 1973 von Ronald Fagin bewiesener Satz aus der deskriptiven Komplexitätstheorie, der aussagt, dass die Menge aller mit Hilfe der existentiellen Prädikatenlogik zweiter Stufe beschreibbaren Sätze genau die Komplexitätsklasse NP ist. Die existentielle Prädikatenlogik zweiter Stufe enthält Sätze, bei denen über die Prädikate eines Satzes aus der Prädikatenlogik erster Stufe existenzquantifiziert wird.Genauer handelt es sich um Sätze der Form (de)
- Le théorème de Fagin est un résultat de théorie de la complexité des algorithmes, montrant l'égalité de la classe NP et de la classe des problèmes exprimables en logique du second ordre existentielle, c'est-à-dire en logique du premier ordre enrichie de quantifications existentielles sur les ensembles. C'est le résultat fondateur de la complexité descriptive. Ce résultat est remarquable, puisqu'il caractérise la classe NP sans avoir recours à une notion de modèle de calcul comme la machine de Turing. On trouve une preuve de ce théorème dans le livre de complexité descriptive de Neil Immerman. (fr)
- Teorema de Fagin é um resultado da, que afirma que o conjunto de todas as propriedades que podem ser expressas na lógica de segunda ordem existencial, é precisamente a classe de complexidade NP. É notável, pois é uma caracterização da classe NP que não invoca um modelo de computação, tal como uma máquina de Turing. (pt)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - Der Satz von Fagin ist ein 1973 von Ronald Fagin bewiesener Satz aus der deskriptiven Komplexitätstheorie, der aussagt, dass die Menge aller mit Hilfe der existentiellen Prädikatenlogik zweiter Stufe beschreibbaren Sätze genau die Komplexitätsklasse NP ist. Die existentielle Prädikatenlogik zweiter Stufe enthält Sätze, bei denen über die Prädikate eines Satzes aus der Prädikatenlogik erster Stufe existenzquantifiziert wird.Genauer handelt es sich um Sätze der Form wobei der Ausdruck nur Quantifizierungen über die Individuenvariablen aber keine Quantifizierungen über die Prädikatvariablen enthält.Die Klasse NP ist die Klasse derjenigen Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine in Polynomialzeit entschieden werden können.Das Bemerkenswerte an diesem Satz ist, dass er eine Komplexitätsklasse nur auf der Basis einer Logik charakterisiert, ohne dabei auf ein Berechnungsmodell wie Turingmaschinen zurückzugreifen. Damit begründete er die deskriptive Komplexitätstheorie. Larry J. Stockmeyer verallgemeinerte das Ergebnis und zeigte, dass die Polynomialzeithierarchie durch die allgemeine Prädikatenlogik zweiter Stufe (mit Allquantoren) beschrieben wird. (de)
- Fagin's theorem is the oldest result of descriptive complexity theory, a branch of computational complexity theory that characterizes complexity classes in terms of logic-based descriptions of their problems rather than by the behavior of algorithms for solving those problems.The theorem states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP. It was proven by Ronald Fagin in 1973 in his doctoral thesis, and appears in his 1974 paper. The arity required by the second-order formula was improved (in one direction) in , and several results of have provided tighter bounds on nondeterministic random-access machines. (en)
- Le théorème de Fagin est un résultat de théorie de la complexité des algorithmes, montrant l'égalité de la classe NP et de la classe des problèmes exprimables en logique du second ordre existentielle, c'est-à-dire en logique du premier ordre enrichie de quantifications existentielles sur les ensembles. C'est le résultat fondateur de la complexité descriptive. Ce résultat est remarquable, puisqu'il caractérise la classe NP sans avoir recours à une notion de modèle de calcul comme la machine de Turing. La preuve de ce résultat fut établie en 1973 par Ronald Fagin dans sa thèse de doctorat. Elle a été depuis reformulée et améliorée, notamment grâce au et à des résultats de Grandjean. On trouve une preuve de ce théorème dans le livre de complexité descriptive de Neil Immerman. (fr)
- Teorema de Fagin é um resultado da, que afirma que o conjunto de todas as propriedades que podem ser expressas na lógica de segunda ordem existencial, é precisamente a classe de complexidade NP. É notável, pois é uma caracterização da classe NP que não invoca um modelo de computação, tal como uma máquina de Turing. Foi provado por Ronald Fagin em 1973, em sua tese de doutorado. A aridade exigida pela fórmula de segunda ordem foi melhorada (em uma direção) no teorema de Lynch, e vários resultados de Grandjean forneceram limitantes mais próximos em máquinas de acesso aleatório não determinísticas . (pt)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is known for
of | |
| is known for
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)