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?
Subscribe to:
Post Comments (Atom)
open problems column link is bad.
ReplyDeleteThanks, fixed
DeleteThese are the most thoughtful PvsNP survey questions that I have yet seen. Thank you GASARCH! :)
ReplyDeleteTo 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).
Is there a closing date for submissions?
ReplyDeleteThanks for the reminder- I added it to the post, Oct 1, 2018
DeleteWhen will the results be published?
ReplyDeleteLane Hemaspaandra's SIGACT NEWS COMPLEXITY COL will have the article. It will be the first issue of SIGACT NEWS in 2019,
Deletewhich I think is March 1, 2019.