Is the complexity of problems in NP exponential at most?

Question

I read on Wikipedia the following:

Since NP-complete problems are in NP, their running time is at most exponential.

Is that correct? I thought a problem is in NP-complete if:

• the problem is also in NP (i.e. accept verification in polynomial time)
• Every problem in NP can be reduced to it in polynomial time.

These two conditions don't necessarily limit (to our knowledge) how hard a problem in NP Complete can be, right? (other than bounding the complexity of verification to polynomial time).

What am I missing?

Answer 1

Intuitively, the difficulty of all $\mathsf{NP}$-Complete problems is related: solving any single $\mathsf{NP}$-Complete problem in time $O(t(n))$ immediately yields an algorithm for any other $\mathsf{NP}$-Complete problem with a running time of $O(t(\mbox{poly}(n)))$. This shows, for example, that either all $\mathsf{NP}$-Complete problems admit polynomial-time algorithms or none of them does.

Your first statement "Since NP-complete problems are in NP, their running time is at most exponential" is NOT a definition of a $\mathsf{NP}$-Complete problem. It is just a property that NP-Complete problems have.

This is equivalent to saying that $\mathsf{NP} \subseteq \mathsf{EXPTIME}$. In fact it is conjectured that the containment is proper, i.e., $\mathsf{NP} \subset \mathsf{EXPTIME}$ . This would imply that there are (decision) problems that can be solved in exponential time but are not in $\mathsf{NP}$. We also know that $\mathsf{P} \subset \mathsf{EXPTIME}$, showing that we must have $\mathsf{NP} \subset \mathsf{EXPTIME}$ if $\mathsf{P}=\mathsf{NP}$.

Answer 2

(other than bounding the complexity of verification to polynomial time).

This is exactly the reason the problems can be solved in exponential time. An algorithm can simply run the verification algorithm for all possible certificates to see if any one of them is a valid "solution". There are only exponentially many certificates since the definition of $NP$ limits the lengths of certificates to be polynomial. Each certificate can be checked in polynomial time, so we can iterate through all possible certificates and check them in exponential time.

Note that for this purpose, "exponential" means $2^{poly(n)}$ so e.g. $2^{n^2}$ counts as exponential.