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.

  1. 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$.
  2. 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.


The issue is that your proposed algorithm is polynomial with respect to the numerical value of the input, but not relative to the input's size. The binary encoding of $N$ requires at most $\lceil\log n\rceil$ bits, so an algorithm which takes the encoding of $N$ and preforms $\Omega(N)$ operations is actually exponential. Such algorithms are said to run in pseudo polynomial time.

Additionally, it seems that you are confusing factoring and primality testing. A possible decision version of factoring is given $(n,x)$ check whether $n$ has a factor $\le x$ (while your proposal refers to the case where only $n$ is given, and you loop to find a possible factor). While checking if a given number is prime is known to be in $P$, FACTORING is believed to lie outside of P.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.