[FOM] Prove something weaker!
Timothy Y. Chow
tchow at alum.mit.edu
Sun Jul 12 16:44:47 EDT 2015
Joe Shipman wrote:
> I'm interested in the phenomenon of famous conjectures being stated in
> strong forms when even very much weaker forms of them are unproven.
> For example, I don't understand why I see a lot more talk about the
> inability to prove that P is not NP, when the inability to prove that P
> is not PSPACE seems far more surprising.
Isn't this obvious? The usual role of "big" conjectures is to outline
what we think should be true, not to demarcate the boundaries of what we
can currently prove. The latter task is primarily of interest to the
experts who are in the trenches trying to push forward the boundary
incrementally. (Though once in a while, non-specialists do get into the
mood of chuckling at how incompetent we all are at the proving business,
in which case the weakest possible conjecture provides the most
> Can anyone supply a technical reason that separating P and PSPACE
> shouldn't be easier to tackle than separating P from NP?
Surely not. But why stop at P vs. PSPACE? Why not ask to show that NEXP
is not contained in P/poly, or that NP has superlinear circuit lower
bounds? That'll get you closer to the current frontier. Ryan Williams
showed in 2010 that NEXP (in fact, NTIME[2^n]) does not have polysize ACC
> I'm also interested in collecting other examples of well-known
> conjectures for which there are much weaker versions that seem almost
> equally difficult to make progress on, besides the two examples above.
I would think that most conjectures fall into this category, but if you
want examples where the gap between what we can prove and what we
conjecture to be true is especially large, then Schanuel's conjecture
comes to mind. So does the entire Langlands program.
More information about the FOM