Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Fagin's_theorem> ?p ?o. }
Showing items 1 to 27 of
27
with 100 items per page.
- Fagin's_theorem 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 1974 (strictly, 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.".
- Fagin's_theorem wikiPageExternalLink fagin.
- Fagin's_theorem wikiPageExternalLink genspec.pdf.
- Fagin's_theorem wikiPageID "3122050".
- Fagin's_theorem wikiPageRevisionID "544192175".
- Fagin's_theorem hasPhotoCollection Fagin's_theorem.
- Fagin's_theorem subject Category:Descriptive_complexity.
- Fagin's_theorem subject Category:Theorems_in_computational_complexity_theory.
- Fagin's_theorem type Abstraction100002137.
- Fagin's_theorem type Communication100033020.
- Fagin's_theorem type Message106598915.
- Fagin's_theorem type Proposition106750804.
- Fagin's_theorem type Statement106722453.
- Fagin's_theorem type Theorem106752293.
- Fagin's_theorem type TheoremsInDiscreteMathematics.
- Fagin's_theorem 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 1974 (strictly, in 1973 in his doctoral thesis).".
- Fagin's_theorem label "Fagin's theorem".
- Fagin's_theorem label "Satz von Fagin".
- Fagin's_theorem label "Théorème de Fagin".
- Fagin's_theorem sameAs Satz_von_Fagin.
- Fagin's_theorem sameAs Théorème_de_Fagin.
- Fagin's_theorem sameAs m.08svnv.
- Fagin's_theorem sameAs Q2226670.
- Fagin's_theorem sameAs Q2226670.
- Fagin's_theorem sameAs Fagin's_theorem.
- Fagin's_theorem wasDerivedFrom Fagin's_theorem?oldid=544192175.
- Fagin's_theorem isPrimaryTopicOf Fagin's_theorem.