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?
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.