7
$\begingroup$

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.

$\endgroup$
  • 15
    $\begingroup$ There's no such thing as "NP-complete for all input data". If the input is fixed, so is the runtime. $\endgroup$ – John Dvorak Mar 20 '17 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$ – Aurelio Mar 20 '17 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 Richerby Mar 20 '17 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 Rasberry Mar 20 '17 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$ – b0fh Mar 22 '17 at 10:51
23
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks @DavidRicherby for the clarification on $\emptyset$ and $\Sigma^*$ $\endgroup$ – jmite Mar 21 '17 at 16:47
13
$\begingroup$

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$.

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
  • $\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$ – Aurelio Mar 20 '17 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$ – Pontus Mar 20 '17 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$ – David Richerby Mar 20 '17 at 13:27
9
$\begingroup$

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{}}$

$\endgroup$
1
$\begingroup$

Graph coloring, maximum clique and maximum independent set are $\mathcal{NP}$-complete (decision versions), but polynomial on perfect graphs.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.