Fifty years of P vs. NP and the possibility of the impossible
L Fortnow - Communications of the ACM, 2021 - dl.acm.org
Communications of the ACM, 2021•dl.acm.org
Fifty years of P vs. NP and the possibility of the impossible Page 1 76 COMMUNICATIONS OF
THE ACM | JANUARY 2022 | VOL. 65 | NO. 1 contributed articles ON MAY 4, 1971, computer
scientist/mathematician Steve Cook introduced the P vs. NP problem to the world in his paper,
“The Complexity of Theorem Proving Procedures.” More than 50 years later, the world is still
trying to solve it. In fact, I addressed the subject 12 years ago in a Communications article,
“The Status of the P versus NP Problem.”The P vs. NP problem, and the theory behind it, has …
THE ACM | JANUARY 2022 | VOL. 65 | NO. 1 contributed articles ON MAY 4, 1971, computer
scientist/mathematician Steve Cook introduced the P vs. NP problem to the world in his paper,
“The Complexity of Theorem Proving Procedures.” More than 50 years later, the world is still
trying to solve it. In fact, I addressed the subject 12 years ago in a Communications article,
“The Status of the P versus NP Problem.”The P vs. NP problem, and the theory behind it, has …
Advances in algorithms, machine learning, and hardware can help tackle many NP-hard problems once thought impossible.