2
$\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$
2
  • 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
  • 6
    $\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$
5
  • 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$ 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
  • 3
    $\begingroup$ OK, but the question asks which of the claims we know to be false. $\endgroup$ Jan 7 '19 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$ Jan 7 '19 at 22:23
7
$\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$
2
  • 1
    $\begingroup$ Yuval's answer is correct. It just focuses on the question, it doesn't solve the whole homework exercise. $\endgroup$ Jan 7 '19 at 22:23
  • 1
    $\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$ Jan 7 '19 at 23:52
0
$\begingroup$

If you take a look at Wikipedia, we find that there is not a clear consensus on what NP-complete actually is. Namely if we define it with what was on Wikipedia for a long time until it was edited out just recently:

A deterministic Turing machine can solve it in large time complexity classes (e.g., EXPTIME, as is the case with brute force search algorithms) and can verify its solutions in polynomial time.

If we assume this definition of NP-complete, then 3 is by definition True and 4 by definition False.

This means that if P=NP then NP-complete is a meaningless definition where no problems actually belong to it.

Hence the definition has been debated as it would seem to collapse down to P-complete in case P=NP if we remove the exponential time hypothesis from the definition.

Since the question asked regarding the current state of knowledge 3 is True and 4 is False as well if we go by the other definition of NP complete.

As for 1 and 2 they are also false in the current state of knowledge.

If it was asked for 1 whether some specific instances of NP-complete problems are solvable in polynomial time, the this is true. There are many cases in fact, where a specific problem instance of SAT for example, turns out to be 2-SAT, or finding the Hamiltonian path in a graph with only n edges, etc. Practical solvers make use of knowledge of specific instances where the NP-complete brute force strategy need not be deployed.

$\endgroup$
10
  • $\begingroup$ There is consensus about the meaning of the term "NP-complete": A decision problem is NP-complete iff (a) it is in NP, and (b) every problem in NP can be transformed into it via a poly-time many-one reduction. If P=NP, then all problems in P are NP-complete. The first section of the Wikipedia page was confusing -- I have tried to improve it just now. $\endgroup$ Mar 29 at 5:16
  • $\begingroup$ This seems like one of those relative definitions where we cannot say anything about problems like travelling salesman, SAT, hamiltonian paths, etc. Sure they all reduce to each other but what if they are in P. And what if there exists some yet unknown NP problem that does not transform to all these known problems. P!=NP but there exists a problem in NP that does not reduce to e.g. SAT. $\endgroup$ Mar 29 at 7:45
  • 1
    $\begingroup$ The definition itself is clear and there's no debate about it. "We cannot say anything" is too strong -- unfortunately we can't say whether P!=NP, but reducibility is something. "what if there exists some yet unknown NP problem that does not transform to all these known problems" -- this doesn't make sense. A problem can be in NP but not NP-complete, and this doesn't create any problems. Also the direction of reductions is from an existing known-NP-complete problem to the problem you are trying to prove NP-complete. $\endgroup$ Mar 29 at 9:03
  • 1
    $\begingroup$ The definition of NP-completeness for decision problems is very clear, and you can find it in various textbooks. Wikipedia is an unreliable source. There is no "controversy". $\endgroup$ Mar 29 at 12:20
  • 1
    $\begingroup$ Cook's theorem, which gives the base case as you say, does not depend on the ETH in any way. I read the first 2 pages of that Barbosa paper. His central claim in Theorem 2.1, that the Cook-Levin theorem is incorrect because $p(n)$ is not given, is itself easily seen to be incorrect: $p(n)$ exists by assumption that the problem being reduced from is in NP. Was this paper published in a respected journal? I suspect not, in which case it is not surprising that no refutation has appeared. $\endgroup$ Mar 30 at 8:06

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.