What are the "hardest" problems which can be solved in polynomial time?

views:

364

answers:

+9 Q:

What are the "hardest" problems which can be solved in 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?)

+8 A:

Primes is in P.

Moron 2010-02-13 20:43:37

+1 Because this was the first answer I thought of after reading the question.

Nixuz 2010-02-13 20:53:48

Nice! Thank you! BTW: Does this has an effect to cryptography?

Karussell 2010-02-13 20:57:37

ah, ok. the "How Practial!?" section already answered this :-)

Karussell 2010-02-13 21:31:45

@Karussell anyway it doesn't have an effect on cryptography. Primality testing is easy. What is difficult is factoring and discrete logarithm; the basic number-theoretic public key cryptosystems depend on these (RSA -- factoring, Diffie-Hellman -- discrete logarith). The practical primality testing algorithms are probabilistic but work in practice very fast.

antti.huima 2010-02-13 21:53:14

+4 A:

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.

antti.huima 2010-02-13 20:52:22

Thanks! There are a lot things I can learn ... can I accept the answer from more than one?

Karussell 2010-02-13 20:58:33

No you can't. And you should keep your question open for about a day, so people have a chance to see it.

ebo 2010-02-13 21:06:01

+3 A:

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

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

Guy 2010-02-13 20:57:47

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

2010-02-13 23:12:40

ok very similar to the problem I mentioned ... only for bipartite graphs. BTW it is older than 1950 ;-) see wikipedia: "In 2006, it was discovered that Carl Gustav Jacobi had solved the assignment problem in the 19th century, and published posthumously in 1890 in Latin."

Karussell 2010-02-14 19:52:21

+1 A:

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.

polygenelubricants 2010-02-28 20:03:26

ansaurus

tags:

views:

answers:

What are the "hardest" problems which can be solved in polynomial time?

related questions