Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Fagins_theorem> ?p ?o }
Showing triples 1 to 39 of
39
with 100 triples per page.
- Fagins_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 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.".
- Fagins_theorem wikiPageExternalLink genspec.pdf.
- Fagins_theorem wikiPageExternalLink fagin.
- Fagins_theorem wikiPageID "3122050".
- Fagins_theorem wikiPageLength "3438".
- Fagins_theorem wikiPageOutDegree "15".
- Fagins_theorem wikiPageRevisionID "670647230".
- Fagins_theorem wikiPageWikiLink Arity.
- Fagins_theorem wikiPageWikiLink Category:Descriptive_complexity.
- Fagins_theorem wikiPageWikiLink Category:Theorems_in_computational_complexity_theory.
- Fagins_theorem wikiPageWikiLink Descriptive_complexity_theory.
- Fagins_theorem wikiPageWikiLink First-order_logic.
- Fagins_theorem wikiPageWikiLink Lexicographical_order.
- Fagins_theorem wikiPageWikiLink Lynchs_theorem.
- Fagins_theorem wikiPageWikiLink NP_(complexity).
- Fagins_theorem wikiPageWikiLink Non-deterministic_Turing_machine.
- Fagins_theorem wikiPageWikiLink Ronald_Fagin.
- Fagins_theorem wikiPageWikiLink Second-order_logic.
- Fagins_theorem wikiPageWikiLink Spectrum_of_a_sentence.
- Fagins_theorem wikiPageWikiLink Springer_Science+Business_Media.
- Fagins_theorem wikiPageWikiLink Turing_machine.
- Fagins_theorem wikiPageWikiLink Étienne_Grandjean.
- Fagins_theorem wikiPageWikiLinkText "Fagin 1974".
- Fagins_theorem wikiPageWikiLinkText "Fagin's theorem".
- Fagins_theorem wikiPageUsesTemplate Template:Cite_book.
- Fagins_theorem wikiPageUsesTemplate Template:Comp-sci-theory-stub.
- Fagins_theorem subject Category:Descriptive_complexity.
- Fagins_theorem subject Category:Theorems_in_computational_complexity_theory.
- Fagins_theorem hypernym Result.
- Fagins_theorem type Theorem.
- Fagins_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 1973 in his doctoral thesis.".
- Fagins_theorem label "Fagin's theorem".
- Fagins_theorem sameAs Q2226670.
- Fagins_theorem sameAs Satz_von_Fagin.
- Fagins_theorem sameAs Théorème_de_Fagin.
- Fagins_theorem sameAs m.08svnv.
- Fagins_theorem sameAs Q2226670.
- Fagins_theorem wasDerivedFrom Fagins_theorem?oldid=670647230.
- Fagins_theorem isPrimaryTopicOf Fagins_theorem.