Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/SO_(complexity)> ?p ?o }
Showing triples 1 to 49 of
49
with 100 triples per page.
- SO_(complexity) abstract "Second-order logic is an extension of first-order with second orders quantifiers, hence the reader should first read FO (complexity) to be able to understand this article. In descriptive complexity we can see that the languages recognised by SO formulae is exactly equal to the language decided by a Turing machine in the polynomial hierarchy. Extensions of SO with some operators also give us the same expressivity than some well known complexity class, so it is a way to do proofs about the complexity of some problems without having to go to the algorithmic level.".
- SO_(complexity) wikiPageExternalLink SO.
- SO_(complexity) wikiPageID "27631008".
- SO_(complexity) wikiPageLength "4394".
- SO_(complexity) wikiPageOutDegree "33".
- SO_(complexity) wikiPageRevisionID "633895095".
- SO_(complexity) wikiPageWikiLink 2-satisfiability.
- SO_(complexity) wikiPageWikiLink Algorithm.
- SO_(complexity) wikiPageWikiLink Category:Computational_complexity_theory.
- SO_(complexity) wikiPageWikiLink Category:Descriptive_complexity.
- SO_(complexity) wikiPageWikiLink Category:Finite_model_theory.
- SO_(complexity) wikiPageWikiLink Co-NP.
- SO_(complexity) wikiPageWikiLink Complexity_class.
- SO_(complexity) wikiPageWikiLink Descriptive_complexity.
- SO_(complexity) wikiPageWikiLink Descriptive_complexity_theory.
- SO_(complexity) wikiPageWikiLink Disjunctive_normal_form.
- SO_(complexity) wikiPageWikiLink EXPTIME.
- SO_(complexity) wikiPageWikiLink FO_(complexity).
- SO_(complexity) wikiPageWikiLink HO_(complexity).
- SO_(complexity) wikiPageWikiLink Horn_clause.
- SO_(complexity) wikiPageWikiLink Krom-clause.
- SO_(complexity) wikiPageWikiLink NL_(complexity).
- SO_(complexity) wikiPageWikiLink NP_(complexity).
- SO_(complexity) wikiPageWikiLink PH_(complexity).
- SO_(complexity) wikiPageWikiLink PSPACE.
- SO_(complexity) wikiPageWikiLink P_(complexity).
- SO_(complexity) wikiPageWikiLink Polynomial_hierarchy.
- SO_(complexity) wikiPageWikiLink Second-order_logic.
- SO_(complexity) wikiPageWikiLink Second_order_logic.
- SO_(complexity) wikiPageWikiLink Turing_machine.
- SO_(complexity) wikiPageWikiLinkText "SO (complexity)".
- SO_(complexity) wikiPageWikiLinkText "Second-order".
- SO_(complexity) wikiPageWikiLinkText "second-order logic over finite structures".
- SO_(complexity) wikiPageWikiLinkText "second-order logic".
- SO_(complexity) wikiPageWikiLinkText "second-order".
- SO_(complexity) hasPhotoCollection SO_(complexity).
- SO_(complexity) wikiPageUsesTemplate Template:Reflist.
- SO_(complexity) subject Category:Computational_complexity_theory.
- SO_(complexity) subject Category:Descriptive_complexity.
- SO_(complexity) subject Category:Finite_model_theory.
- SO_(complexity) hypernym Extension.
- SO_(complexity) type Software.
- SO_(complexity) comment "Second-order logic is an extension of first-order with second orders quantifiers, hence the reader should first read FO (complexity) to be able to understand this article. In descriptive complexity we can see that the languages recognised by SO formulae is exactly equal to the language decided by a Turing machine in the polynomial hierarchy.".
- SO_(complexity) label "SO (complexity)".
- SO_(complexity) sameAs m.0c41cv7.
- SO_(complexity) sameAs Q7392162.
- SO_(complexity) sameAs Q7392162.
- SO_(complexity) wasDerivedFrom SO_(complexity)?oldid=633895095.
- SO_(complexity) isPrimaryTopicOf SO_(complexity).