patternMinor
Can we reduce an NP complete item to an NP item which is $\bf{non}$ P?
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?
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.
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.