About: Fagin's theorem     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:WikicatMathematicalTheorems, within Data Space : dbpedia.org associated with source document(s)
QRcode icon
http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FFagin%27s_theorem

Fagin's theorem is a result in descriptive complexity theory that states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP. It is remarkable since it is a characterization of the class NP that does not invoke a model of computation such as a Turing machine. It was proven by Ronald Fagin in 1973 in his doctoral thesis. The arity required by the second-order formula was improved (in one direction) in Lynch's theorem, and several results of Grandjean have provided tighter bounds on nondeterministic random-access machines.

AttributesValues
rdf:type
rdfs:label
  • Satz von Fagin
  • Fagin's theorem
  • Théorème de Fagin
  • Teorema de Fagin
rdfs:comment
  • Fagin's theorem is a result in descriptive complexity theory that states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP. It is remarkable since it is a characterization of the class NP that does not invoke a model of computation such as a Turing machine. It was proven by Ronald Fagin in 1973 in his doctoral thesis. The arity required by the second-order formula was improved (in one direction) in Lynch's theorem, and several results of Grandjean have provided tighter bounds on nondeterministic random-access machines.
  • 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
  • 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 d'une quantification existentielle 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 machine comme la machine de Turing. On peut trouver une preuve de ce théorème dans le livre de complexité descriptive de Neil Immerman.
  • Teorema de Fagin é um resultado da teoria da complexidade descritiva, 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.
sameAs
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Link from a Wikipage to an external page
foaf:isPrimaryTopicOf
prov:wasDerivedFrom
has abstract
  • Fagin's theorem is a result in descriptive complexity theory that states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP. It is remarkable since it is a characterization of the class NP that does not invoke a model of computation such as a Turing machine. It was proven by Ronald Fagin in 1973 in his doctoral thesis. The arity required by the second-order formula was improved (in one direction) in Lynch's theorem, and several results of Grandjean have provided tighter bounds on nondeterministic random-access machines.
  • 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.
  • 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 d'une quantification existentielle 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 machine 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 théorème de Lynch et à des résultats de Grandjean. On peut trouver une preuve de ce théorème dans le livre de complexité descriptive de Neil Immerman.
  • Teorema de Fagin é um resultado da teoria da complexidade descritiva, 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 .
http://purl.org/voc/vrank#hasRank
http://purl.org/li...ics/gold/hypernym
is Link from a Wikipage to another Wikipage of
is Wikipage redirect of
is Wikipage disambiguates of
is foaf:primaryTopic of
is known for of
Faceted Search & Find service v1.17_git39 as of Aug 09 2019


Alternative Linked Data Documents: PivotViewer | iSPARQL | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 07.20.3232 as of Aug 9 2019, on Linux (x86_64-generic-linux-glibc25), Single-Server Edition (61 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2019 OpenLink Software