3
$\begingroup$

I'm following an online course which has the following (multiple-choice) quiz question:

Which of the following statements cannot be true, given the current state of knowledge?

  1. Some NP-complete problems are polynomial-time solvable, and some NP-complete problems are not polynomial-time solvable.
  2. There is an NP-complete problem that is polynomial-time solvable.
  3. There is an NP-complete problem that can be solved in $ O(n^{\log n}) $ time, where $ n $ is the size of the input.
  4. There is no NP-complete problem that can be solved in $ O(n^{\log n}) $ time, where $ n $ is the size of the input.

It seems to me that (1) and (2) are false since it has not been proven that any NP-complete problem is polynomial-time solvable. So I'm vacillating between (3) and (4).

In particular, I'm a bit nonplussed where the $O(n^{\log n})$ comes from; I haven't seen this expression in any of the lecture notes. However, I do know about the traveling salesman problem which can be solved in $O(n^2 2^n)$ time using the Held-Karp algorithm. It would seem to me like this function grows less faster asymptotically than $O(n^{\log n})$, since it is usually the expression in the exponent that matters the most, in which case the answer would be (3).

Is this correct? Also, how would I show this formally?

$\endgroup$
  • 3
    $\begingroup$ I think you need to read the question again. It asks what cannot be true. $\endgroup$ – D.W. Sep 21 '17 at 17:31
  • 5
    $\begingroup$ I had missed that indeed. It turns out that neither (3) or (4) are the correct answer; I believe that (1) is the correct answer (though I haven't yet verified this) because by definition if one NP-complete problem is solvable in polynomial time, then all of them are. $\endgroup$ – Kurt Peek Sep 22 '17 at 11:00
3
$\begingroup$

The Exponential Time Hypothesis (ETH) states that SAT cannot be solved in time $2^{o(n)}$. Now suppose that $A$ is some NP-complete problem which can be solved in time $O(n^{\log n})$. Since $A$ is NP-hard, there is a polytime reduction from SAT to $A$, say running in time $O(n^k)$. Using this reduction, we can solve SAT in time $O(n^{k^2 \log n})$, contradicting ETH.

Since ETH is still standing, it is safe to assume that no $O(n^{\log n})$ algorithm is known for any NP-complete problem. We don't know for sure that (3) is true, i.e. we don't know for sure that (4) is false.

Conversely, we can't prove that no $O(n^{\log n})$ algorithm is known for any NP-complete problem. So we don't know for sure that (3) is false either.

$\endgroup$
  • 1
    $\begingroup$ Most of the time, the $n$ in ETH stands for the number of variables, while the $n$ in the running time of an np hardness reduction stands for the total input size, right? Can you clarify? $\endgroup$ – user53923 Sep 21 '17 at 22:33
  • $\begingroup$ Yes, you are right. But that shouldn't make a big difference here (exercise). $\endgroup$ – Yuval Filmus Sep 22 '17 at 6:47
  • $\begingroup$ I agree that it should not make a big difference $\endgroup$ – user53923 Sep 22 '17 at 7:47
  • 2
    $\begingroup$ OK, but the question asks which of the claims we know to be false. $\endgroup$ – David Richerby Jan 7 at 14:13
  • $\begingroup$ This answer would be better if you also explained why we can't rule out the existence of an $O(n^{\log n})$ algorithm for an NP-complete problem. $\endgroup$ – Gilles Jan 7 at 22:23
4
$\begingroup$

The accepted answer is incorrect. I've taken the same course, and option 1 is correct. They didn't say why, but I have the following argument.

Quoting Wikipedia:

polynomial time: An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., $ T(n) = O(n^k) $ for some positive constant $ k $.

exponential time: An algorithm is said to be exponential time, if $ T(n) $ is upper bounded by $ 2^{poly(n)} $, where $ poly(n) $ is some polynomial in $ n $. More formally, an algorithm is exponential time if $ T(n) $ is bounded by $ O(2^{n^k}) $ for some constant $ k $.

We don't know $ P \neq NP $, so option 2 can't be ruled out.

For all we know, the running time required to solve NP-complete problems could be anywhere between polynomial and exponential (note that $ n^{\log n} $ is more than polynomial but less than exponential). Thus, options 3 and 4 can't be ruled out.

That only leaves option 1. The claim in option 1 is incorrect because if there's a polynomial-time algorithm for any NP-complete problem X, then every other NP problem has a polynomial-time algorithm by reduction to X.

$\endgroup$
  • $\begingroup$ Yuval's answer is correct. It just focuses on the question, it doesn't solve the whole homework exercise. $\endgroup$ – Gilles Jan 7 at 22:23
  • $\begingroup$ @Gilles, It wasn't correct until your edit. The original claim was misleading and led to believe that option 4 was the correct answer. Your comment misrepresents what was; either your edit should stand, or your comment, because making an edit and commenting on what doesn't exist anymore makes no sense. $\endgroup$ – Abhijit Sarkar Jan 7 at 23:52

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.