Matches in DBpedia 2014 for { <http://dbpedia.org/resource/NP-intermediate> ?p ?o. }
Showing items 1 to 26 of
26
with 100 items 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. Some problems that are considered good candidates for being NP-intermediate are the graph isomorphism problem, factoring, and computing the discrete logarithm.Another problem in NP that is not known to be in P or NP-complete is the minimum circuit size problem (MCSP). Unlike the above problems, MCSP is believed to be NP-complete. However, proving as much via a many-one reduction will imply circuit lower bounds for E (unless NP is contained in SUBEXP, which is a violation of the exponential time hypothesis). Therefore, proving that MCSP is NP-complete is considered outside of current techniques.".
- NP-intermediate wikiPageExternalLink 200039297.
- NP-intermediate wikiPageExternalLink section5.ps.
- NP-intermediate wikiPageID "4637081".
- NP-intermediate wikiPageRevisionID "598223220".
- NP-intermediate hasPhotoCollection NP-intermediate.
- NP-intermediate subject Category:Complexity_classes.
- NP-intermediate type Abstraction100002137.
- NP-intermediate type Class107997703.
- NP-intermediate type Collection107951464.
- NP-intermediate type ComplexityClasses.
- NP-intermediate type Group100031264.
- 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-Intermedio".
- NP-intermediate label "NP-intermediate".
- NP-intermediate label "Problem NP-pośredni".
- NP-intermediate label "Satz von Ladner".
- 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 sameAs NP-intermediate.
- NP-intermediate wasDerivedFrom NP-intermediate?oldid=598223220.
- NP-intermediate isPrimaryTopicOf NP-intermediate.