patternMajor
Can a subset of an NP-complete problem be in P?
Viewed 0 times
problemcansubsetcomplete
Problem
The problem is NP-complete (proven) for all input data (without exception).
We assume that P != NP.
Is it possible that there is an (infinitely large) subset of the problem, for which this subset is in P?
Theoretical question.
We assume that P != NP.
Is it possible that there is an (infinitely large) subset of the problem, for which this subset is in P?
Theoretical question.
Solution
Your question doesn't make sense:
The problem is NP-complete (proven) for all input data (without exception).
This is not a thing. NP-completeness is a property of entire sets, not of specific inputs. It's fairly trivial to show that, if you choose a specific input, any problem is $O(1)$ on that input: you just output yes or no, depending which is correct for your input. When you do this, all of algorithm analysis breaks down and everything ends up useless. So, we don't do this.
$P$, $NP$, $NP$-completeness, polynomial time, etc. are all related to asymptotic complexity: as the size of input grows, how does the run-time grow? This only makes sense when you look across different input, the same way the derivative of a point in calculus is a property that takes into account the curve surrounding the point.
We assume that P != NP.
Again, this doesn't affect your answer. If $P = NP$, then every $P$ set is $NP$-complete,* so there are a bunch of subsets in $P$. And if $P=NP$, the examples that people have given are all valid.
Is it possible that there is a subset of the problem (infinitely large), that this problem is in P?
Yes, and the other answers have given great examples of this. But for posterity, here's yet another counter example.
Except for $\emptyset$ and $\Sigma^$, which aren't $NP$-complete for technical reasons relating to the form of reductions we use to define completeness.
The problem is NP-complete (proven) for all input data (without exception).
This is not a thing. NP-completeness is a property of entire sets, not of specific inputs. It's fairly trivial to show that, if you choose a specific input, any problem is $O(1)$ on that input: you just output yes or no, depending which is correct for your input. When you do this, all of algorithm analysis breaks down and everything ends up useless. So, we don't do this.
$P$, $NP$, $NP$-completeness, polynomial time, etc. are all related to asymptotic complexity: as the size of input grows, how does the run-time grow? This only makes sense when you look across different input, the same way the derivative of a point in calculus is a property that takes into account the curve surrounding the point.
We assume that P != NP.
Again, this doesn't affect your answer. If $P = NP$, then every $P$ set is $NP$-complete,* so there are a bunch of subsets in $P$. And if $P=NP$, the examples that people have given are all valid.
Is it possible that there is a subset of the problem (infinitely large), that this problem is in P?
Yes, and the other answers have given great examples of this. But for posterity, here's yet another counter example.
- $k$-coloring is $NP$-complete if you take $k$ as input, but $2$-coloring is an infinite subset of this that is in $P$.
Except for $\emptyset$ and $\Sigma^$, which aren't $NP$-complete for technical reasons relating to the form of reductions we use to define completeness.
Context
StackExchange Computer Science Q#71805, answer score: 23
Revisions (0)
No revisions yet.