# NP-completeness of a problem with pretty fast algorithm

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?

• Does this answer your question? Are there subexponential-time algorithms for NP-complete problems? – Tassle Jan 26 '20 at 8:47
• 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. – 1.. Jan 26 '20 at 9:00

## 1 Answer

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