Problems that are hard to prove in $\mathcal{P}$ What is the famous "hard" problems that were shown to be in $\mathcal{P}$ after?

I want to know a list of problems that are difficult to prove in the class of "easy" problems?

Maybe like matching, linear programming. Any list or references would be appreciated.
The famous primality testing problem, shown to be in P in the 2000 paper PRIMES is in P.