Guest Column: The Third P =? NP Poll (SIGACT News Complexity Theory Column 100)

In 2012 there were many more P6 =NP proponents than in 2002. In 2019 there were just a few more. In 2019 everyone was either EQUAL or NOT-EQUAL. Gone are the clever people who say Ind of ZFC! or I don’t know and I don’t care! I do not know (though I do care) if the lack of unusual answers is due to a maturing of the field or to the fact that Surveymonkey didn’t quite allow for other answers. A few of the comments in 2019 looked like they wanted to say IND, DK, or DC, but not many. I really do think the field has matured, and so have the responders. Of course, saying that voting IND, DK, or DC is immature reveals my bias, which could be wrong. Dmytro Taranovsky points out that we really don’t know: NO. While I agree with the consensus view, there is a substantial uncertainty on the issue: We fundamentally do not understand computation. Natural classes tend to be comparable and we cannot rule out that this applies to complexity classes as well. Andr´as Salamon thinks P6 =NP but they are nearly equal: NO. My working hypothesis is that NL6=NP [NL is Nondeterministic Log Space] with a lower probability then P6=NP[I prefer stating the converse: P=NP is more likely than NL=NP.] However, it seems clear that finding the hard regions is itself hard, so I aim to spend one in every ten working days exploring the consequences of the hypothesis that P=NP, since we seem to live in a world where P is “nearly equal to” NP for practical purposes (not because problems in NP are “easy,” but because P contains really hard problems by the Deterministic Time Hierarchy theorem). Lance Fortnow is more sure that P6 =NP: NO. People that think P=NP are like people who think Elvis is still alive. [Maybe Elvis will prove P=NP.] 2.2 When Will P=?NP Be Resolved? The following is a chart of the responses to the question When Will P=?NP Be Resolved? The years are 2000+ unless it is written in full. So 02–09 means 2002–2009 but 2200–3000 means 2200–3000. 02–09 10–19 20–29 30–39 40–49 50–59 60–69 70–79 2002 5 (5%) 12 (12%) 13 (13%) 10 (10%) 5 (5%) 12 (12%) 4 (4%) 0 (0%) 2012 0 (0%) 2 (1%) 17 (11%) 18 (12%) 5 (3%) 10 (6.5%) 10 (6.5%) 9 (6%) 2019 0 (0%) 0 (0%) 26 (22%) 20 (17%) 14 (12%) 9 (7%) 7 (6%) 5 (4%) 80–89 90–99 100–109 110–119 150–159 2200–3000 4000–4100 2002 1 (1%) 0 (0%) 0 (0%) 0 (0%) 0 (0%) 5 (5%) 0 (0%) 2012 4 (3%) 5 (3%) 2 (1.2%) 5 (3%) 2 (1.2%) 3 (2%) 3 (2%) 2019 0 (0%) 0 (0%) 1 (0.8%) 10 (12%) 10 (12%) 1 (0.8%) 11 (9%) Long Time Never Don’t Know Sooner than 2100 Later than 2100 2002 0 (0%) 5 (5%) 21 (21%) 62 (62%) 17 (17%) 2012 22 (14%) 5 (3%) 8 (5%) 81 (53%) 63 (41%) 2019 7 (6%) 11 (9%) 0 (0%) 84 (66%) 40 (34%)