Tuesday, August 31, 2010

Does P = NP?

Not that I had heard abou this question/problem before, but it is fun for geeks. Basically, can computers solve all problems? Or at least NP type problems, because they can P type problems. Or put another way (from the article):

"P"-class problems are "easy" for computers to solve; that is, solutions to these problems can be computed in a reasonable amount of time compared to the complexity of the problem. Meanwhile, for "NP" problems, a solution might be very hard to find--perhaps requiring billions of years' worth of computation--but once found, it is easily checked. (Imagine a jigsaw puzzle: finding the right arrangement of pieces is difficult, but you can tell when the puzzle is finished correctly just by looking at it.)

It's not the end of the world if P not equal NP, as most computer scientists think, because you can still create workarounds, apparently.

Via geekpress