13
$\begingroup$

Assume $P\neq NP$.

What can we say about the runtime bounds of all NP-complete problems?

i.e. what are the tightest functions $L,U:\mathbb{N}\to\mathbb{N}$ for which we can guarantee that an optimal algorithm for any NP-complete problem runs in time of at least $\omega(L(n))$ and at most $o(U(n))$ on a input of length $n$?

Obviously, $\forall c:L(n)=\Omega(n^c)$. Also, $U(n) = O(2^{n^{\omega(1)}})$.

Without assuming $QP\neq NP$, $ETH$, or any other assumption which is not implied by $P\neq NP$, can we give any better bounds on $L,U$?

EDIT:

Note that at least one of $L,U$ has to be far from the bounds I gave here, since being NPC problems, these problems has poly time reduction between each other, meaning that if some NPC problem has an optimal algorithm of time $f(n)$, then all problems has an algorithm (optimal or not) of runtime $O(f(n^{O(1)}))$.

Improve this question
$\endgroup$
4
  • $\begingroup$ if P$\neq$NP we can say that the runtime bounds are larger than any polynomial.... afaik no, better bounds are not known.... a lot of notation doesnt chg that... there do exist superpolynomial-but-subexponential functions eg $2^{\log n}$ $\endgroup$
    – vzn
    Commented Mar 12, 2014 at 16:37
  • $\begingroup$ First, $2^{\log n}$ is just linear, so I guess you mean $2^{polylog(n)}$ which is known as the class $QP$. I fully realize that $P\neq NP$ doesn't mean any NP-complete function will run at exponential time, but that is not what I'm asking. For example, assuming $P\neq NP$, is it possible that a NPC problem can be solved in $2^{log(n)\cdot log^*(n)}$, where $log^*(n)$ is the inverse Ackermann function? The notations are merely a tool used for expressing my question formally.. $\endgroup$
    – R B
    Commented Mar 12, 2014 at 17:14
  • $\begingroup$ thx for the correction. very little is known in this area afaik. try this question NTime(n^k) =? DTime(n^k) tcs.se $\endgroup$
    – vzn
    Commented Mar 12, 2014 at 17:28
  • $\begingroup$ @RB While it is true that in each "possible world" there are lower and upper bounds which are roughly within a polynomial of each other, it is not clear what a priori bounds are possible. $\endgroup$
    – Yuval Filmus
    Commented Mar 16, 2014 at 19:05

1 Answer 1

Reset to default
2
$\begingroup$

My interpretation of the question is that is asks about the possibilities in relativized worlds. Suppose that in some relativized world, $P \neq NP$. Can we deduce anything non-trivial about the time complexity of NP-complete problems? The Baker–Gill–Solovay argument shows that we can "force" some NP problem to require exponential time, so the upper bound given in the question is essentially optimal.

Regarding the lower bound, we sketch below a proof that relative to some oracle, $NP = \mathrm{TIME}(2^{O(\log^2 n)})$. Assuming that the sketched proof is correct, we can also apply it to functions smaller than $2^{O(\log^2 n)}$, and this shows that the lower bound given in the question is also essentially tight.

Proof sketch. We construct two oracles $O_1,O_2$: the first behaves like a $\mathrm{TIME}(2^{O(\log^2 n)})$-complete problem, and the second implements the Baker–Gill–Solovay diagonalization. It is straightforward to pack both oracles into a single oracle.

The oracle $O_1$ consists of all pairs $\langle M, x \rangle$ such that $M$ is an oracle Turing machine that accepts $x$ in running time $2^{2^{\sqrt{\log |x|}}}$ when given access to the oracles $O_1,O_2$ restricted to inputs of length at most $2^{\sqrt{\log |x|}}$. (This is not a circular definition.)

The oracle $O_2$ is defined in the same way that the oracle is defined in Baker–Gill–Solovay: for each clocked oracle Turing machine $M$ running in time $T = 2^{o(\log^2 n)}$, we find some input length $n$ which is "untouched", run $M$ on $1^n$ for $T$ steps, and for each query to $O_2$ of size $n$, we mark that this input is not in $O_2$ (for other queries we also mark that the input is not there, unless we had already decided that it is in $O_2$). Queries to $O_1$ are handled similarly (as implicit queries to $O_1,O_2$ of smaller size, handled recursively); notice that such queries never mention strings of length $n$ in $O_2$, since $2^{\sqrt{\log T}} < n$. If the machine accepts, we mark all other strings of length $n$ in $O_2$ as missing, otherwise we pick some string of length $n$ and put it in $O_2$.

The class $P^{O_1,O_2}$ consists of all programs running in time $2^{2^{O(\sqrt{\log n})}}$, making queries to $O_1,O_2$ of size $2^{O(\sqrt{\log n})}$. The class $NP^{O_1,O_2}$ is of the form $x \mapsto \exists |y|<n^C \varphi(x,y)$, where $\varphi \in P^{O_1,O_2}$, and so it is contained in the class of all programs running in time $2^{n^C}$ and making oracle queries of size $2^{O(\sqrt{\log n})}$. The latter is contained in $\mathrm{TIME}(2^{\log^2 n^C})^{O_1,O_2}$, since we can use $O_1$ to decide it. This shows that $NP^{O_1,O_2} \subseteq \mathrm{TIME}(2^{O(\log^2 n)})^{O_1,O_2}$.

For the other direction, let $L$ be the language which consists of $1^n$ for each $n$ such that $O_2$ contains some string of length $n$. By construction of $O_2$, $L \notin \mathrm{TIME}(2^{o(\log^2 n)})^{O_1,O_2}$, while clearly $L \in NP^{O_1,O_2}$. This shows that $NP^{O_1,O_2} = \mathrm{TIME}(2^{O(\log^2 n)})^{O_1,O_2}$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I have to admint I didn't fully understand your answer, but if, as you mentioned, some NP-complete problem $\Pi$ is only solvable in $\Omega(2^{n^c})$, then all other NPC problems are also only solvable in $\Omega(2^{n^{\Omega(1)}})$, as there's a poly time reduction to them from $\Pi$, which means that otherwise you'd have a better algorithm for $\Pi$. This implies for example $QP\neq NP$ and $ETH$ doesn't it? What am I missing? $\endgroup$
    – R B
    Commented Mar 12, 2014 at 7:59
  • $\begingroup$ Well, it doesn't imply $ETH$, but it does look it may imply $QP\neq NP$. $\endgroup$
    – R B
    Commented Mar 12, 2014 at 8:11
  • $\begingroup$ You're not missing anything. There is a relativized world in which ETH is true. There is another relativized world where P=NP, and so in particular ETH is false. $\endgroup$
    – Yuval Filmus
    Commented Mar 12, 2014 at 11:41
  • $\begingroup$ But not in all reletivized worlds in which $P\neq NP$, $QP\neq NP$ is true as well, right? There is a chance that $P\subsetneq QP = NP$. From what I understood from your answer, if $P\neq NP$ there exist a NPC problem whose lower bound is exponential, and I'm wondering why it's true. $\endgroup$
    – R B
    Commented Mar 12, 2014 at 11:54
  • 1
    $\begingroup$ In my answer I (purportedly) give a relativized world in which $NP = \mathrm{TIME}(n^{O(\log n)})$. Another relativized world has $NP = \mathrm{TIME}(2^{n^{O(1)}})$. In yet other relativized worlds, $P=NP$. Regarding $QP$, I don't claim anything about it. $\endgroup$
    – Yuval Filmus
    Commented Mar 12, 2014 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.