If You Solve This Math Problem, You Could Steal All the Bitcoin in the World

A diagram showing the relevant complexity classes in the P vs NP problem. “P” problems are solvable in polynomial time; “NP” problems might be solvable in polynomial time, and are checkable in polynomial time. “NP-complete” problems are NP problems such that finding a solution to them would let you solve every NP problem. “NP hard” problems are problems at least as complex as the NP-complete problems. Phew.
Graphic: Behnam Esfahbod (Wikimedia Commons)

You may have heard of the famous P versus NP problem. If you can prove or disprove its cryptically short equation, you’d be a million dollars richer—and maybe even billions of dollars richer, depending on your scruples.

The importance of P versus NP is mainly in its consequences for computing. It happens to be one of the seven Millennium Prize Problems, meaning The Clay Mathematics Institute of Cambridge, Massachusetts will award $1 million to whomever manages to prove or disprove the statement. But should you prove that P in fact does equal NP, you wouldn’t even need the $1 million prize. As theoretical computer scientist Scott Aaronson explained last week at a lecture in a stuffy auditorium at Los Alamos National Lab in New Mexico, proving that P=NP would open up some intriguing possibilities.

“If someone proves P=NP, the first thing they should do is steal $200 billion in bitcoin. The second thing they should do is solve all of the other Millennium Prize Problems,” Aaronson said.

To understand this, you need to know that computers are devices that solve problems, abstracted into code readable by the physical computing device, based on the principles put forth by Alan Turing. Solving problems takes a number of steps and a certain amount of time, with the amount of time required increasing as the problem grows larger.

“P” refers to the problems that computers solve all the time, from something as simple as multiplying two numbers to more complex tasks like browsing the internet. As a…

Source Link