# What are some problems in the class P which we used to think were in the class of NP?

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?

• 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? Commented Jan 24, 2018 at 13:31

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.