Why does nondeterministically estimating a number have exponential time complexity?

Question

One way to determine whether a number is prime is to try all possible integers less than that number and see whether any are divisors, also called factors. That algorithm has exponential time complexity because the magnitude of a number is exponential in its length

In Sipser's book, this explanation is given for finding whether an integer is prime or not.

There are exponential number of integers to test but why can't the nondeterministic TM just estimate the number bit by bit, like it does in estimating a solution to the satisfiability problem?

It can just estimate each bit and if any of the branches returns true, then it accepts that branch as the number associated with that branch divides the input.

We know that there exists a nondeterministic TM that decides the class PRIME. If my argument is wrong, what would be the correct NTM that decides the language?

Answer 1

First, Sipser was talking about a deterministic algorithm, not a non-deterministic one.

Second, the machine you describe does not solve the problem $\texttt{PRIME}$, because it returns true when it finds a divisor of the integer. That means that it is solving $\overline{\texttt{PRIME}}$ (the complement problem), and shows that $\texttt{PRIME}\in \text{co}\mathsf{NP}$, not that $\texttt{PRIME}\in \mathsf{NP}$.

Third, actually, it was proven in 2002 (AKS) that $\texttt{PRIME} \in \mathsf{P}$, so there is indeed a deterministic polynomial time algorithm to test for primality, but it is much more complex that testing all potential divisors, and relies on heavy maths.