2
$\begingroup$

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?

$\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
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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