• June 2011
    M T W T F S S
    « May   Jul »

The Million-Dollar Puzzle That Could Change the World

 New Scientist (06/01/11) Jacob Aron

 The single biggest problem in computer science, for which the Clay Mathematics Institute is offering a $1 million prize to whoever solves it, is determining whether P equals NP, which raises the issue that computation has a fundamental, innate limitation that goes beyond hardware.  The complexity class of NP, or non-deterministic polynomial time, is comprised of problems whose solutions are difficult to come by but can be confirmed in polynomial time.  All problems in the set P also can be found in the set NP, but the core of the P=NP? problem is whether the reverse also applies.  If P turns out not to be equal to NP, it demonstrates that some problems are so involved naturally that crunching through them is impossible, and validating this theory would gain insight on the performance of the latest computing hardware, which divides computations across multiple parallel processors, says the University of Massachusetts, Amherst’s Neil Immerman.  The field of cryptography also could be affected by this proof, as even the toughest codes would be cracked by a polynomial-time algorithm for solving NP problems.  On the other hand, finding an algorithm to solve an NP-complete problem would enable any NP problem to be solved in polynomial time, establishing a universal computable solution.  This could support the creation of algorithms that execute near-perfect speech recognition and language translation, and that facilitate computerized visual information processing equal to that of humans.



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: