Sign In

Communications of the ACM

ACM News

Tide Turns Against Million-Dollar Maths Proof

View as: Print Mobile App Share:

Initially hailed as a solution to the biggest question in computer science, the latest attempt to prove P ≠ NP—otherwise known as the "P vs NP" problem—seems to be running into trouble.

Two prominent computer scientists have pointed out potentially "fatal flaws" in the draft proof by Vinay Deolalikar of Hewlett-Packard Labs in Palo Alto, California.

Since the 100-page proof exploded onto the Internet a week ago, mathematicians and computer scientists have been racing to make sense of it.

The problem concerns the speed at which a computer can accomplish a task, such as factorising a number. Roughly speaking, P is the set of problems that can be computed quickly, while NP contains problems for which the answer can be checked quickly.

From New Scientist

View Full Article


No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account