In Quantum Information and Quantum Computation by Nielsen and Chuang, they define the complexity class NP as follows (page 142):
A language $L$ is in NP if there is a turing machine $M$ with the following properties.
- If $x\in L$ then there exists a witness string $w$ such that $M$ halts in the state $q_Y$ ("yes state") after a time polynomial in $|x|$ when the machine is started in the state $x$-blank-$w$.
- If $x \not \in L$ then for all strings $w$ which attempt to play the role of a witness, the machine halts in state $q_N$ ("no state") after a time polynomial in $|x|$ when $M$ is started in the state $x$-blank-$w$.
This definition is motivated by the factoring decision problem, where they identify "witness strings" $w$ with possible factors of $x$.
My confusion is, based on how NP is defined, it seems like we are able to construct a polynomial time algorithm for solving the factoring decision problem. For a given string $x$, start the factoring turing machine $M$ in the state $x$-blank-$w$ for all $w < x$, and check whether the machine ever halts in $q_Y$. Since there are $O(|x|)$ witnesses to check, and for each witness, the machine will halt in polynomial time, it follows that this algorithm will determine whether $x$ has factors in polynomial time.
Clearly this shouldn't work, but I am unsure where the flaw in my logic is.