This HTML5 document contains 71 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbpedia-dehttp://de.dbpedia.org/resource/
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n7https://books.google.com/
n21https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-pthttp://pt.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbpedia-frhttp://fr.dbpedia.org/resource/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:NP_(complexity)
dbo:wikiPageWikiLink
dbr:Fagin's_theorem
Subject Item
dbr:Dependence_logic
dbo:wikiPageWikiLink
dbr:Fagin's_theorem
Subject Item
dbr:Descriptive_Complexity
dbo:wikiPageWikiLink
dbr:Fagin's_theorem
Subject Item
dbr:Descriptive_complexity_theory
dbo:wikiPageWikiLink
dbr:Fagin's_theorem
Subject Item
dbr:Mathematical_logic
dbo:wikiPageWikiLink
dbr:Fagin's_theorem
Subject Item
dbr:Spectrum_of_a_sentence
dbo:wikiPageWikiLink
dbr:Fagin's_theorem
Subject Item
dbr:Northwest_Classen_High_School
dbo:wikiPageWikiLink
dbr:Fagin's_theorem
Subject Item
dbr:Fagin_theorem
dbo:wikiPageWikiLink
dbr:Fagin's_theorem
dbo:wikiPageRedirects
dbr:Fagin's_theorem
Subject Item
dbr:Second-order_logic
dbo:wikiPageWikiLink
dbr:Fagin's_theorem
Subject Item
dbr:Monadic_second-order_logic
dbo:wikiPageWikiLink
dbr:Fagin's_theorem
Subject Item
dbr:SNP_(complexity)
dbo:wikiPageWikiLink
dbr:Fagin's_theorem
Subject Item
dbr:Fagin's_theorem
rdf:type
yago:WikicatTheoremsInComputationalComplexityTheory yago:Statement106722453 yago:Theorem106752293 yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Proposition106750804 yago:WikicatMathematicalTheorems
rdfs:label
Théorème de Fagin Teorema de Fagin Satz von Fagin Fagin's theorem
rdfs:comment
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. 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. 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. 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
dcterms:subject
dbc:Theorems_in_computational_complexity_theory dbc:Descriptive_complexity
dbo:wikiPageID
3122050
dbo:wikiPageRevisionID
1069424639
dbo:wikiPageWikiLink
dbr:Non-deterministic_Turing_machine dbc:Descriptive_complexity dbr:Descriptive_complexity dbr:Lexicographical_order dbr:Lynch's_theorem dbr:Spectrum_of_a_sentence dbr:Springer-Verlag dbr:Arity dbr:First-order_logic dbr:Étienne_Grandjean dbr:Second-order_logic dbr:Computational_complexity_theory dbr:NP_(complexity_class) dbr:Ronald_Fagin dbc:Theorems_in_computational_complexity_theory
dbo:wikiPageExternalLink
n7:books%3Fid=004anbcFjnwC&pg=PA43
owl:sameAs
dbpedia-fr:Théorème_de_Fagin dbpedia-pt:Teorema_de_Fagin freebase:m.08svnv wikidata:Q2226670 dbpedia-de:Satz_von_Fagin n21:26j1d yago-res:Fagin's_theorem
dbp:wikiPageUsesTemplate
dbt:Cite_conference dbt:Cite_book dbt:Short_description
dbo:abstract
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. 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 . 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. 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.
gold:hypernym
dbr:Result
prov:wasDerivedFrom
wikipedia-en:Fagin's_theorem?oldid=1069424639&ns=0
dbo:wikiPageLength
4147
foaf:isPrimaryTopicOf
wikipedia-en:Fagin's_theorem
Subject Item
dbr:Finite_model_theory
dbo:wikiPageWikiLink
dbr:Fagin's_theorem
Subject Item
dbr:Ronald_Fagin
dbo:wikiPageWikiLink
dbr:Fagin's_theorem
dbp:knownFor
dbr:Fagin's_theorem
dbo:knownFor
dbr:Fagin's_theorem
Subject Item
wikipedia-en:Fagin's_theorem
foaf:primaryTopic
dbr:Fagin's_theorem