Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/NP-intermediate> ?p ?o }
Showing triples 1 to 51 of
51
with 100 triples per page.
- NP-intermediate abstract "In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate, and the class of such problems is called NPI. Ladner's theorem, shown in 1975 by Richard Ladner, is a result asserting that, if P ≠ NP, then NPI is not empty; that is, NP contains problems that are neither in P nor NP-complete. Since the other direction is trivial, we can say that P = NP if and only if NPI is empty.Under the assumption that P ≠ NP, Ladner explicitly constructs a problem in NPI, although this problem is artificial and otherwise uninteresting. It is an open question whether any "natural" problem has the same property: Schaefer's dichotomy theorem provides conditions under which classes of constrained Boolean satisfiability problems can not be in NPI. Some problems that are considered good candidates for being NP-intermediate are the graph isomorphism problem, factoring, and computing the discrete logarithm.".
- NP-intermediate wikiPageExternalLink 200039297.
- NP-intermediate wikiPageExternalLink section5.ps.
- NP-intermediate wikiPageID "4637081".
- NP-intermediate wikiPageLength "6241".
- NP-intermediate wikiPageOutDegree "20".
- NP-intermediate wikiPageRevisionID "664143440".
- NP-intermediate wikiPageWikiLink Category:Complexity_classes.
- NP-intermediate wikiPageWikiLink Circuit_minimization_for_Boolean_functions.
- NP-intermediate wikiPageWikiLink Complexity_class.
- NP-intermediate wikiPageWikiLink Computational_complexity_theory.
- NP-intermediate wikiPageWikiLink Discrete_log_problem.
- NP-intermediate wikiPageWikiLink Discrete_logarithm.
- NP-intermediate wikiPageWikiLink Factoring_integers.
- NP-intermediate wikiPageWikiLink Graph_isomorphism_problem.
- NP-intermediate wikiPageWikiLink Group_automorphism.
- NP-intermediate wikiPageWikiLink Group_isomorphism.
- NP-intermediate wikiPageWikiLink Group_isomorphism_problem.
- NP-intermediate wikiPageWikiLink Integer_factorization.
- NP-intermediate wikiPageWikiLink NP-complete.
- NP-intermediate wikiPageWikiLink NP-completeness.
- NP-intermediate wikiPageWikiLink NP_(complexity).
- NP-intermediate wikiPageWikiLink P_(complexity).
- NP-intermediate wikiPageWikiLink P_=_NP_problem.
- NP-intermediate wikiPageWikiLink P_versus_NP_problem.
- NP-intermediate wikiPageWikiLink Ring_automorphism.
- NP-intermediate wikiPageWikiLink Ring_homomorphism.
- NP-intermediate wikiPageWikiLink Ring_isomorphism.
- NP-intermediate wikiPageWikiLink Schaefers_dichotomy_theorem.
- NP-intermediate wikiPageWikiLink VC_dimension.
- NP-intermediate wikiPageWikiLinkText "NP-intermediate".
- NP-intermediate wikiPageWikiLinkText "intermediate complexity".
- NP-intermediate hasPhotoCollection NP-intermediate.
- NP-intermediate wikiPageUsesTemplate Template:Cite_web.
- NP-intermediate wikiPageUsesTemplate Template:ComplexityZoo.
- NP-intermediate wikiPageUsesTemplate Template:Reflist.
- NP-intermediate subject Category:Complexity_classes.
- NP-intermediate hypernym NP-intermediate.
- NP-intermediate type Article.
- NP-intermediate type Article.
- NP-intermediate type Class.
- NP-intermediate comment "In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate, and the class of such problems is called NPI. Ladner's theorem, shown in 1975 by Richard Ladner, is a result asserting that, if P ≠ NP, then NPI is not empty; that is, NP contains problems that are neither in P nor NP-complete.".
- NP-intermediate label "NP-intermediate".
- NP-intermediate sameAs Satz_von_Ladner.
- NP-intermediate sameAs NP-Intermedio.
- NP-intermediate sameAs Problem_NP-pośredni.
- NP-intermediate sameAs m.0cdvrq.
- NP-intermediate sameAs Q1130846.
- NP-intermediate sameAs Q1130846.
- NP-intermediate wasDerivedFrom NP-intermediate?oldid=664143440.
- NP-intermediate isPrimaryTopicOf NP-intermediate.