We are in a rut. We seem to have the urge to show a theorem is hard to prove rather than to actually prove it! To be fair, many of our conjectures are hard to prove. Even so, we need to get out of this rut. I list several problems that I think can be solved with current techniques. For each one I will say why the current barrier techniques might not apply.
- Prove that NP not equal to EXP=DTIME(2O(n)). There are oracles for proper containment either way, and for incompatibility (see this paper) but there are no oracles for which they are equal. Also note that NP is robust and EXP is not. That might be useful. DO NOT TRY TO FIND AN ORACLE TO MAKE THEM EQUAL!!! THAT IS THE MENTALITY I WANT TO BREAK US OUT OF!!!
- How do NL and P compare? There are oracles to make either properly contained in the other (see this paper). However, Relativized (spellcheck made me capitalize Relativized) space has several definitions and its not clear which one is appropriate (Jonathan Buss's and Ruzzo-Simon-Tompa have worked on this). DO NOT TRY TO FIND THE RIGHT DEFINITION OF RELATIVIZED SPACE!!! JUST PROVE A CONTAINMENT EITHER WAY!!! IT DOESN"T EVEN HAVE TO BE PROPER!!! OR PROVE THEY ARE THE SAME (unlikely).
- Is NL properly contained in PSPACE? Of course it is, but lets PROVE IT rather than REDEFINE ORACLES to prove that its hard (some of the same comments for NL and P apply here).
-
Lets look at Nondeterminism in a different light- for rather powerful classes and rather weak ones.
- Let PR be the set of SETS that are Prim Rec, and NPR be the set of all SETS that are Nondet Prim Rec. Is PR=NPR? DO NOT TRY TO DEFINE PRIM REC WITH ORACLES TO OBTAIN A BARRIERS RESULT!!!! JUST SOLVE THE DAMN PROBLEM!!!
- Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA). Do they recognize the same set of languages or not? DO NOT DEFINE DFA'S WITH ORACLES!!! DO NOT TRY TO MAKE DFA's FIT INTO THE NAT PROOFS FRAMEWORK!!! JUST SOLVE THE BLEEPING PROBLEM!!!!
Isn't 4.2 known? DFAs with 2^q states can simulate NFA's with q states. I think this simulation is known to be tight.
ReplyDeleteWhat did you mean in 4.2?
adam
I think 4.2 should be numbered 4.1 because that's what it is :P. Happy April Fool's Day!
ReplyDeleteIt's a testament to Bill's "style" that it is (NP-)hard to distinguish between Bill's real posts and his april fool's day posts ..
ReplyDeleteWell, if EXP = DTIME(2^O(n)), anything is true...
ReplyDeleteI prove that NP is not equal to DTIME(2^{O(n)} below:
ReplyDeleteNP is closed under polynomial time m-one-reductions.
On the other hand, DTIME(2^{O(n)}
is not closed under polynomial time m-one reductions.
Therefore, NP is not equal to
DTIME(2^{O(n)}).
One of major open problems in complexity
is to separate NP from EXP=DTIME(2^{n^{O(1)}).
Bin
Um, isn't NL contained in PSPACE immediate from Savitch's Theorem?
ReplyDeleteOh for proper containment you need the space hierarchy theorem too I guess.
ReplyDeleteHmmmm ... it seems to me that GASARCH's point-of-view can invigorate pretty much any discipline ... for example ...
ReplyDelete-------------------
We complexity(quantum) theorists seem more concerned with proving that we can't prove (simulate) things than with actually proving (simulating) things !!!!
We are in a rut. We seem to have the urge to show a theorem (system) is hard to prove (simulate) rather than to actually prove (simulate) it!
To be fair, many of our conjectures (quantum models) are hard to prove (simulate). Even so, we need to get out of this rut.
While on the subject of invigorating the field, what are your thoughts on the future of theoretical computer science? Are you seeing an increase or decrease in undergraduates interested in theoretical computer science? An increase or decrease in graduate school applications to your departments? Do you feel that attitudes towards funding for theory are getting more positive or more negative from within your faculty, and from funding agencies? Are people from other disciplines more or less aware of theory than they were in the past? What countries do you think will emerge as theory hot spots in the future? ect ect... It would be great if a wide range of theorists could share their observations.
ReplyDeleteFor 4.1,
ReplyDeleteI think they are equal. NPR is an existential quantifier bounded by a PR in front of a PR predicate. Since you can do PR bounded search in PR, you can compute it in PR.
A general comment, the unprovability results like BGS and RR were by people who were trying to solve the problems. In rephrasing what Sasha said in the first barriers workshop, the natural proof barrier was intended to guide people in proving lower bounds and how to solve the open problems.
ReplyDeleteDear past and future commenters:
ReplyDeletenote the date that this post was made.
bill gasarch