# Is there an NP-complete problem that can be solved in $O(n^{\log n})$ time?

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?

• I think you need to read the question again. It asks what cannot be true. – D.W. Sep 21 '17 at 17:31
• 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. – Kurt Peek Sep 22 '17 at 11:00

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.

• 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? – user53923 Sep 21 '17 at 22:33
• Yes, you are right. But that shouldn't make a big difference here (exercise). – Yuval Filmus Sep 22 '17 at 6:47
• I agree that it should not make a big difference – user53923 Sep 22 '17 at 7:47
• OK, but the question asks which of the claims we know to be false. – David Richerby Jan 7 '19 at 14:13
• 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. – Gilles 'SO- stop being evil' Jan 7 '19 at 22:23

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.

• Yuval's answer is correct. It just focuses on the question, it doesn't solve the whole homework exercise. – Gilles 'SO- stop being evil' Jan 7 '19 at 22:23
• @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. – Abhijit Sarkar Jan 7 '19 at 23:52