10

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

Mathew Thompson
  • 55,877
  • 15
  • 127
  • 148
Karussell
  • 17,085
  • 16
  • 97
  • 197
  • I would ask for problems with a high lower bound in P. – ebo Feb 13 '10 at 21:00
  • IMHO a bound couldn't and shouldn't compared *accross* different types of algorithms or what do you mean with lower bound? – Karussell Feb 13 '10 at 21:10
  • Probably true, but it's not a very scientific question either ;-) Lower bound: The problem has a lower bound of Omega(n**x). – ebo Feb 13 '10 at 21:14
  • yes, it is not scientific, but I learned a lot :-) and in the case of my cited "P-hard" problem the complexity has a relative low lower bound: ~O(n^3) ... and what if there are more than one dependent variables m,L, ... ? – Karussell Feb 13 '10 at 21:35

5 Answers5

10

Primes is in P.

  • +1 Because this was the first answer I thought of after reading the question. – Nixuz Feb 13 '10 at 20:53
  • Nice! Thank you! BTW: Does this has an effect to cryptography? – Karussell Feb 13 '10 at 20:57
  • ah, ok. the "How Practial!?" section already answered this :-) – Karussell Feb 13 '10 at 21:31
  • @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 Feb 13 '10 at 21:53
6

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
  • 25,136
  • 3
  • 52
  • 71
  • Thanks! There are a lot things I can learn ... can I accept the answer from more than one? – Karussell Feb 13 '10 at 20:58
  • 1
    No you can't. And you should keep your question open for about a day, so people have a chance to see it. – ebo Feb 13 '10 at 21:06
5

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

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

Guy
  • 14,178
  • 27
  • 67
  • 88
3

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
  • 376,812
  • 128
  • 561
  • 623
2

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

  • 1
    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 Feb 14 '10 at 19:52