[FOM] Prove something weaker!
Joe Shipman
joeshipman at aol.com
Mon Jul 13 00:16:45 EDT 2015
My worry is that emphasis on the "big" conjectures might retard progress by discouraging people from working on much weaker questions, especially with techniques that might not be promising for generalization to the "big" conjecture but which would still represent a major advance in what we know.
I had been under the impression that there were partial results in the Langlands program, which has the advantage of being more than just one big conjecture.
Schanuel's conjecture is an interesting case because it is basically saying that a certain structure is free, so it's hard to think of what a partial result might look like (maybe "no nontrivial relations of syntactic length N" for some small N?).
-- JS
Sent from my iPhone
> On Jul 12, 2015, at 4:44 PM, Timothy Y. Chow <tchow at alum.mit.edu> wrote:
>
> 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 amusement.)
>
>> 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 circuits.
>
>> 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.
>
> Tim
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
More information about the FOM
mailing list