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.