CODEWITHSUNDEEP
algorithmtime-complexitynp-hard
Karussell
Karussell

Reputation: 17375

What are the "hardest" problems using polynomial time?

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

Upvotes: 10

Views: 3105

Answers (5)

polygenelubricants
polygenelubricants

Reputation: 383956

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.

Upvotes: 3

PythonPower
PythonPower

Reputation:

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

Upvotes: 2

Guy
Guy

Reputation: 14830

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

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

Upvotes: 5

Antti Huima
Antti Huima

Reputation: 25542

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.

Upvotes: 6

Aryabhatta
Aryabhatta

Reputation:

Primes is in P.

Upvotes: 10

Related Questions