[FOM] P =? NP: A practically important breakthrough

[Joe Shipman]

This doesn't seem to make it more plausible that the specific well-defined statement P=NP is false. I disagree that the random oracle results are the ones that are "practically important", because if there is a fast classical algorithm for SAT it would have colossal practical consequences.

-- JS

-----Original Message-----
From: Kreinovich, Vladik <vladik at utep.edu>
To: Foundations of Mathematics <fom at cs.nyu.edu>
Sent: Wed, Jan 13, 2016 1:19 pm
Subject: [FOM] P =? NP: A practically important breakthrough

 
From the practical viewpoint, the P =? NP problem is almost
solved: a 2015 breakthrough
 
At the 56th Annual Symposium on Foundations of Computer Science
FOCS'2015, organized by the IEEE Computer Society, the Best Paper
Award was given to a paper "An average-case depth hierarchy
theorem for Boolean circuits" by Benjamin Rossman, Rocco A.
Servedio, and Li-Yang Tan (pp. 1030-1048 in the conference
proceedings). Their main result is that for a random oracle A,
with probability 1, all the classes Sent from my iPhone
are different -- in particular, the relativized classes NP^A and
P^A are different.
 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160113/2ec89f4e/attachment.html>