PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Medium Entry average rating: No information on entry rating
NP-complete (Definition)

A problem $\pi\in\mathcal{NP}$ is $\mathcal{NP}$ complete if for any $\pi^\prime\in\mathcal{NP}$ there is a Cook reduction of $\pi^\prime$ to $\pi$ Hence if $\pi\in\mathcal{P}$ then every $\mathcal{NP}$ problem would be in $\mathcal{P}$ A slightly stronger definition requires a Karp reduction or Karp reduction of corresponding decision problems as appropriate.

A search problem $R$ is $\mathcal{NP}$ hard if for any $R^\prime\in\mathcal{NP}$ there is a Levin reduction of $R^\prime$ to $R$




"NP-complete" is owned by Henry.
(view preamble | get metadata)

View style:

Other names:  NP complete, NP hard
Also defines:  NP-hard
Log in to rate this entry.
(view current ratings)

Cross-references: Levin reduction, search problem, decision problems, Karp reduction, stronger, Cook reduction
There are 5 references to this entry.

This is version 1 of NP-complete, born on 2002-09-06.
Object id is 3429, canonical name is NPComplete.
Accessed 9206 times total.

Classification:
AMS MSC68Q15 (Computer science :: Theory of computing :: Complexity classes )

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)