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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.