NP-intermediate

NP-intermediate

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,[1] 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, however 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 in 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 in NP-complete is considered outside of current techniques.[2]

A large list of natural problems with potentially intermediate complexity has been created by users of Theoretical Computer Science Stack Exchange.[3]

References

  1. ^ Ladner, Richard (1975). "On the Structure of Polynomial Time Reducibility". Journal of the ACM (JACM) 22 (1): 155–171. doi:10.1145/321864.321877. 
  2. ^ Kabanets, Valentine; Cai, Jin-Yi (2000), "Circuit minimization problem", Proc. 32nd Symposium on Theory of Computing, Portland, Oregon, USA, pp. 73–79, doi:10.1145/335305.335314, ECCC TR99-045 .
  3. ^ Lev Reyzin, Problems Between P and NPC, (version: 2011-08-20).

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Intermediate consumption — is an economic concept used in national accounts, such as the United Nations System of National Accounts (UNSNA) and the US National Income and Product Accounts (NIPA). Conceptually, the aggregate intermediate consumption is equal to the amount… …   Wikipedia

  • Intermediate uveitis — refers to inflammation localized to the vitreous and peripheral retina. Primary sites of inflammation include the vitreous of which other such entities as pars planitis, posterior cyclitis, and hyalitis are encompassed. Intermediate uveitis may… …   Wikipedia

  • Intermediate — (dt. Intermediat, von mlat. intermediātus „Zwischenprodukt“, „Zwischenglied“) steht für: Intermediate (Bereifung), ein Rennreifen Typ Intermediate Bulk Container, ein Transportcontainer für Flüssigkeiten Intermediate Care, eine Intensiv Abteilung …   Deutsch Wikipedia

  • Intermediate scrutiny — Intermediate scrutiny, in U.S. constitutional law, is the middle level of scrutiny applied by courts deciding constitutional issues through judicial review. The other levels are typically referred to as rational basis review (least rigorous) and… …   Wikipedia

  • Intermediate sanctions — is a term used in regulations enacted by the United States Internal Revenue Service that is applied to non profit organizations who engage in transactions that inure to the benefit of a disqualified person within the organization. These… …   Wikipedia

  • Intermediate — In ter*me di*ate, a. [Pref. inter + mediate: cf. F. interm[ e]diat.] 1. Lying or being in the middle place or degree, or between two extremes; coming or done between; intervening; interposed; interjacent; as, an intermediate space or time;… …   The Collaborative International Dictionary of English

  • Intermediate state — Intermediate In ter*me di*ate, a. [Pref. inter + mediate: cf. F. interm[ e]diat.] 1. Lying or being in the middle place or degree, or between two extremes; coming or done between; intervening; interposed; interjacent; as, an intermediate space or …   The Collaborative International Dictionary of English

  • Intermediate terms — Intermediate In ter*me di*ate, a. [Pref. inter + mediate: cf. F. interm[ e]diat.] 1. Lying or being in the middle place or degree, or between two extremes; coming or done between; intervening; interposed; interjacent; as, an intermediate space or …   The Collaborative International Dictionary of English

  • Intermediate tie — Intermediate In ter*me di*ate, a. [Pref. inter + mediate: cf. F. interm[ e]diat.] 1. Lying or being in the middle place or degree, or between two extremes; coming or done between; intervening; interposed; interjacent; as, an intermediate space or …   The Collaborative International Dictionary of English

  • Intermediate good — Intermediate goods or producer goods are goods used as inputs in the production of other goods, such as partly finished goods or raw materials. A firm may make then use intermediate goods, or make then sell, or buy then use them. In the… …   Wikipedia

  • Intermediate filament — Intermediate filaments (IFs) are cytoskeletal structures formed by members of a family of related proteins called keratin. Intermediate filaments have a diameter of 12 nanometers, which is between that of actin (microfilaments) and microtubules.… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”