patternMinor
Is there an NP-complete problem that can be solved in $O(n^{\log n})$ time?
Viewed 0 times
problemcanlogtimecompletethatsolvedthere
Problem
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?
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?
Which of the following statements cannot be true, given the current
state of knowledge?
- Some NP-complete problems are polynomial-time solvable, and some NP-complete problems are not polynomial-time solvable.
- There is an NP-complete problem that is polynomial-time solvable.
- There is an NP-complete problem that can be solved in $ O(n^{\log n}) $ time, where $ n $ is the size of the input.
- 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?
Solution
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.
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.
Context
StackExchange Computer Science Q#81487, answer score: 7
Revisions (0)
No revisions yet.