Exhaustive search algorithms for np-complete problems
$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.