What are the “hardest” problems using polynomial time?

Question

Recently I read a seminar work which says:

The matching algorithm [for general graphs] can be extended to the weighted case, which appears to be one of the "hardest" combinatorial optimization problems that can be solved in polynomial time.

Immediately the following question came to my mind:

Do you know other "P-hard" problems?

For now I would like to define P-hard as: "A polynomial algorithm was found very late (after 1950) in the literature for that problem". (Or how could one better define "hard" if there is already a deterministic algorithms which solves the problem in polynomial time?)

Answer 1

There are actually "P-complete" problems, which means that every other problem that can be computed in polynomial time can be reduced to them. See http://en.wikipedia.org/wiki/P-complete.

Answer 2

Primes is in P.

Answer 3

Another "hard" P problem is solving "linear programming":

http://en.wikipedia.org/wiki/Linear_programming#Algorithms

Answer 4

If you want to bend the rules a bit, then pseudo-polynomial time algorithms are the "hardest" that you can solve in "polynomial time".

A classic example of a pseudo-polynomial algorithm is the O(nW) dynamic programming solution to the knapsack problem.

Answer 5

The Assignment Problem which can be solved in O(n³) by the modified Hungarian Algorithm.