Supposing if a problem with $n$ non-deterministic bits is in $O(2^{\alpha n})$ time at every $\alpha\in(0,1)$ then is there evidence that problem can or cannot be $\mathsf{NP}$-complete?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Does this answer your question? Are there subexponential-time algorithms for NP-complete problems? $\endgroup$ – Tassle Jan 26 '20 at 8:47
-
$\begingroup$ Don't think so. Here non-determinism is given to be $n$ and though input bits is $n$ non-deterministic bits is $n^\gamma$ at a $\gamma\in(0,1)$ with is fixed and thus the limit of the exponent in terms of non-deterministic bits is $\alpha n$ at any $\alpha>0$ here and there $\alpha=\Omega(1)$ holds (for example with clique reduction non-determinism is $\sqrt{n}$). Thus it appears $\mathsf{ETH}$ is violated if it were $\mathsf{NP}$ complete. $\endgroup$ – 1.. Jan 26 '20 at 9:00
Add a comment
|
$\begingroup$
$\endgroup$
Yes, such problems can be NP-complete.
Consider classical NP-complete graph problems like clique.
Clique has an $O(2^n)$ time algorithm, where $n$ is the number of vertices. However the input for clique is the adjacency matrix of the graph, which has $n^2$ bits. Therefore when the size of input is measured in bits, clique has an $O(2^\sqrt{n})$ time algorithm, which is $O(2^{\alpha n})$ for any positive $\alpha$.
