The status of the P versus NP problem

By Lance Fortnow. CACM, 2009

337 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Limits on fundamental limits to computation (2014, background): “Researchers have ruled out entire categories of proof techniques as insufficient to complete such a proof [76, 95].”
Most Tensor Problems Are NP-Hard (2009, result): “s is whether quantum computers might help with these problems. This is believed unlikely because of the seminal works [Bernstein and Vazirani 1997] and [Fortnow and Rogers 1999] (see also the survey [Fortnow 2009]). These authors have demonstrated that the complexity class of bounded error quantum p”
Quantum machine learning: a classical perspective (2017, background): “Recall that NP-hard is a class of problems for which there is strong evidence of a separation with P [162].”