Monday, July 09, 2018

Soliciting answers for THIRD survey about P vs NP

I have done two surveys for SIGACT NEWS Complextiy Column (edited by Lane Hemaspaandra)
on P vs NP and related topics.  Lane has asked me to do a third. I annouced it in my open problems column here For those who don't read SIGACT news

1) You should!

2) Here is where to go to fill out the survey: here

bill g.

P.S. (do people use P.S. anymore? Do young people know that it means Post Script, and that it
does not refer to ps-files?)

A commenter requested I add what the DEADLINE for responding was. I originally thought people would read the post and immediately respond (and I HAVE had a BIG uptick in responses in the last day). I still believe this. BUT there are people who read the blog days, weeks, months, even years after I post it (though the comments we get on very old posts tend to contain clicks for good deals on Tuxedo's (I am serious. Tuxedo's? Not well targeted unless they count my Tuxedo T-shirt).

Okay, enough babbling -- the point is that I should have a deadline for those who read the blog later than now.

DEADLINE: Oct 1, 2018. STRICT!

P.P.S - does anyone use P.P.S anymore?


  1. open problems column link is bad.

  2. These are the most thoughtful PvsNP survey questions that I have yet seen. Thank you GASARCH! :)

    To assist us non-specialists, perhaps you might provide references that explain the notation and historical background of question #12. E.g., what does the notation "\(1^c\)" indicate?

    As for historical background, we can start with Juris Hartmanis:

    Results about the complexity of algorithms change quite radically if we consider only properties of computations which can be proven formally.

    As a concrete example, Emanuele Viola's answer to the TCS StackExchange question "Are runtime bounds in P decidable? (answer: no)" plausibly entangles (AFAICT anyway) Survey Question #12 with Hartmanis' observation.

    Needless to say, there exist plenty more natural-yet-unanswered questions in complexity theory that exhibit Hartmanis-esque entanglements … it is this entanglement that makes Survey Question #12 so enjoyably thought-provoking (for me anyway).

  3. Is there a closing date for submissions?

    1. Thanks for the reminder- I added it to the post, Oct 1, 2018

  4. When will the results be published?

    1. Lane Hemaspaandra's SIGACT NEWS COMPLEXITY COL will have the article. It will be the first issue of SIGACT NEWS in 2019,
      which I think is March 1, 2019.