Communications of the ACM
Tide Turns Against Million-Dollar Maths Proof
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
No entries found