Exhaustive search algorithms for np-complete problems Somewhere in the forum (a question about p vs np) I read that no exhaustive search algorithm exists for np-complete problems with better time complexity than $2^N$, however the subset sum problem has an algorithm with worst case complexity $O(2^{N/2}$), this looks much better than $2^N$, what is wrong with this?
$O(2^{n/2})$ is still $\mathcal{EXP}$.

The claim you report is known as the exponential-time hypothesis and is a stronger statement than $\mathcal{P} \neq \mathcal{NP}$. We don't actually know if it's true or not.