3
$\begingroup$

Say we want to factor a large number.

Factoring it is in NP.

Verifying it is definitely in P.

However, how do we know that there is no other factors besides the one we found?

So it seems that verifying it isn't in NP either.

Now I am getting confused with NP definition here. I know that NP includes all P.

But then there is this side definition that NP are problems with polynomial verifier.

Is there a proof that all NP problems have P verifier?

If the answer is true, yes all NP problems and hence all NP complete problems have P verifier, then please tell me the proof.

|cite|improve this question
$\endgroup$
  • 13
    $\begingroup$ The title of the question does not seem to match the body. $\endgroup$ – jwodder May 19 '17 at 15:52
18
$\begingroup$

A problem is in NP if and only if it has a polynomial verifier – that's the definition of NP. All NP-complete problems are in NP – that's part of the definition – and so have a polynomial verifier.

Factoring is not a decision problem, so it neither belongs to NP nor doesn't belong to NP. You can turn Factoring into a decision problem in many ways, for example asking if the $i$th bit of the $j$th factor of $n$ is equal to $b$. In that case a witness will be the list of factors of $n$. We can check that the factors multiply to $n$, and that they are all prime (since primality testing is in polynomial time).

(We are using here the unique factorization theorem, stating that a positive integer can be factored as a product of primes in a unique way. The same property doesn't hold in some more general situations.)

It is suspected that the decision problem corresponding to Factoring is not NP-complete, though it is certainly in NP, as the preceding paragraph shows.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ There are primality proofs which can be verified with a simpler and faster algorithm than the fastest known deterministic primality test. $\endgroup$ – kasperd May 19 '17 at 23:15
1
$\begingroup$

Veryfying means that you have factored number correctly.

If you have factored number $C$ as $C = A_1 * A_2 * ... * A_n$ you can check if it's right by simply calculating ${\displaystyle \prod_{i=1}^{n} A_i}$ and testing if all $A$ are primes in polynomial time.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

The N in NP stands for non-deterministic, the P for polynomial.

An non-deterministic polynomial algorithm can be expressed as a verifier where each choice for a non-deterministic step is part of the input. Simulating that is polynomial in the number of steps taken.

This means that every NP problem has a polynomial verifier.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Oh so all NP problem have polynomial verifier. And that's the proof? Can I see that more. It seems that the "answer" to be "verified" must be a simulation of NP. What about if I want normal answer. For example, say I want to know if 3 and 7 is the prime factor that is farthest from the edge. $\endgroup$ – user4951 May 20 '17 at 19:56
  • $\begingroup$ a correct path through the simulation would include a list of choices made at each point the NP Turing machine could have made more than one. You can feed that list of choices into the verifier to get a polynomial time verification. $\endgroup$ – ratchet freak May 20 '17 at 20:01

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.