HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Can we reduce an NP complete item to an NP item which is $\bf{non}$ P?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
itemcannonreducecompletewhich

Problem

I'm curious if we can reduce an $NP$-complete problem to an $NP$ problem which is not a part of the $P$ set. Meaning, can we take an algorithm for this kind of $NP$ problem and use it to solve a single $NP$-complete problem?

If we could do this would it mean that the single $NP$ problem which is non $P$ is considered to be a part of the $NP$-complete problem set?

Is there a way to prove that all $NP$ problems which are non $P$ are considered to be a part of the $NP$-complete problem set?

Solution

No, it is not possible to prove that all $NP$ problems which are not $P$ are $NP$-complete. In fact, the opposite has been shown: unless $P=NP$, there are $NP$ intermediate problems, neither in $P$, nor $NP$-complete. See https://en.wikipedia.org/wiki/NP-intermediate

So if you reduce an $NP$-complete problem to another $NP$ problem, all you've done is proved that that problem is also $NP$-complete.

Context

StackExchange Computer Science Q#59754, answer score: 8

Revisions (0)

No revisions yet.