0
$\begingroup$

I was recently watching a video on the classes of P and NP, in which it was claimed that there have been 'several' problems that were presumed to be in the class of NP, which have since been shown to be in the class of P. Unfortunately, no examples of such problems were given. Could anyone verify this statement by providing an example of such a problem?

$\endgroup$
1
  • 1
    $\begingroup$ Every problem in P is also in NP. One correct version of your question is: What are some problems in P which we used to think were not in P? Another is: What are some problems in P which we used to think were NP-complete? $\endgroup$ Jan 24 '18 at 13:31
3
$\begingroup$

Consider the following problem $A$: given $n$, is $n$ a composite integer (i.e., not a prime)?

It is easy to prove that $A$ is in NP: any nontrivial divisor acts as a certificate.

Proving that $A$ is also in P is much harder, and it is equivalent to proving that its complement, i.e. primality, is in P as well. Still, this has now been proved.

$\endgroup$

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.