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.
$\begingroup$
$\endgroup$
9
-
16$\begingroup$ There's no such thing as "NP-complete for all input data". If the input is fixed, so is the runtime. $\endgroup$– John DvorakCommented Mar 20, 2017 at 11:58
-
$\begingroup$ Input not have fixed size. Input grows linearly, and the execution time increases exponentially (NP-complete of this problem X is proved). $\endgroup$– AurelioCommented Mar 20, 2017 at 12:08
-
9$\begingroup$ Please don't post the same question to multiple Stack Exchange sites. It's against site policy because it fragments answers and it wastes the time that people spend answering questions that have been answered elsewhere. $\endgroup$– David RicherbyCommented Mar 20, 2017 at 13:23
-
$\begingroup$ If I have my notions correct on the following example and am correctly interpreting the intent of your question, you could consider SATISFIABILITY vs. 2-SAT. The former is in NP-Complete, while the latter is in P. You can even stretch this to NP-Hardness: finding a solution of minimal support to $Ax=b$ is NP-Hard in general, but is done quite quickly if you restrict $A$ to be an element of the set of invertible matrices (the minimal weight solution would be the unique solution). $\endgroup$– Thomas RasberryCommented Mar 20, 2017 at 20:09
-
$\begingroup$ I think he key insight here, about why the question does not make sense, is not input size bounds, but rather the fact that NP-completeness asserts that for all inputs of the problem being reduced, there exists a reduction to your problem (with a corresponding input). It's not something universally quantified over the input of the problem being reduced to. $\endgroup$– b0fhCommented Mar 22, 2017 at 10:51
|
Show 4 more comments
6 Answers
$\begingroup$
$\endgroup$
1
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.
- $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.
answered Mar 20, 2017 at 18:07
-
$\begingroup$ Thanks @DavidRicherby for the clarification on $\emptyset$ and $\Sigma^*$ $\endgroup$ Commented Mar 21, 2017 at 16:47
$\begingroup$
$\endgroup$
In fact, you don't need the P$\,\neq\,$NP hypothesis, since there are even infinite constant-time decidable subsets of NP-complete problems. For any NP-complete language $L\subseteq\{0,1\}^*$, let $L' = \{0w\mid w\in L\}\cup\{1w\mid w\in\{0,1\}^*\}$. $L'$ is still NP-complete (trivial reduction from $L$), but it contains the infinite constant-time decidable subset of all strings beginning with $1$.
answered Mar 20, 2017 at 13:35
$\begingroup$
$\endgroup$
3
As I understand your question, yes, this is possible. As an example, consider the (infinitely large) subset of SAT that contains all satisfiable formulae with no negations. This subset is trivially in P.
-
$\begingroup$ Misunderstood. SAT is just an example. I wrote that for all cases is NP-complete. SAT class P is if it fulfills the conditions of Schaefer's dichotomy theorem (en.wikipedia.org/wiki/Schaefer%27s_dichotomy_theorem). There is a condition mentioned by you. But what if it turns out that there is a subset of the class P and does not belong (this subset) to Schaefer's dichotomy theorem? $\endgroup$– AurelioCommented Mar 20, 2017 at 12:35
-
$\begingroup$ Now I have no idea what you are asking. I think you need to edit and clarify your original question. $\endgroup$– PontusCommented Mar 20, 2017 at 12:40
-
7$\begingroup$ @Aurelio The class of negation-free formulas is exactly what you asked for: an infinite polynomial-time decidable subproblem of an NP-complete problem. If you were looking for something else, you need to edit your question. $\endgroup$ Commented Mar 20, 2017 at 13:27
$\begingroup$
$\endgroup$
Take the example of $\mathsf{3\text{-}Coloring}$ problem, it is $\mathsf{NP\text{-}Complete}$ in general, but for trees (there are infinitely many ) it is in $\mathsf{P\text{}}$
$\begingroup$
$\endgroup$
Graph coloring, maximum clique and maximum independent set are $\mathcal{NP}$-complete (decision versions), but polynomial on perfect graphs.
$\begingroup$
$\endgroup$
Take the Travelling Salesman problem: Given are n cities, and the distances between each pair of cities, and a limit d. Is there a route touching each city once and then returning to the starting point with a total length ≤ d?
For any set of cities and distances, for small values of d ("small" depending on the distances) it will be easy to show that there is no solution, and for large values of d it is easy to find a solution. So you can find a subset of the problem where d is large or small enough where you can solve any instance in polynomial time.
