patternModerate
Do all NP complete problem have polynomial verifier?
Viewed 0 times
problemverifierpolynomialallcompletehave
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#75618, answer score: 18
Revisions (0)
No revisions yet.