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!!!!