[FOM] Shipman seeks weaker complexity separations

[Sam Buss]

> From: joeshipman at aol.com
> To: FOM at cs.nyu.edu
> Cc:
> Date: Fri, 10 Jul 2015 17:56:22 -0400
> Subject: [FOM] Prove something weaker!
> 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.

There is a good deal of reasearch directed at proving weaker forms of P not
equal to NP.  A prime exanple is the use of alternation trading proofs:
this has a variety of goals but is in essence trying to separate Logspace
(or other sublinear space classes) from NP.  The best result to-date is
that simulataneous n^c time and n^{o(1)} algorithms cannot solve
satiisfiability problems.  For this with c=2 cos(pi/7), see Williams. For a
proof that 2 cos(pi/7) cannot be improved with current techniques see my
paper with Williams:

Ryan Williams, "Alternation Tading Proofs, Linear Programming and Lower
Bounds"
S. Buss and R. Williams, "Limits on Alternation-Trading Proofs for
Time-Space Lower Bounds"

An example in the *other* direction is the proof that NL=coNL
(NL=nondeterministic log time)
of Immerman-Scelepcseny.  This can be viewed as a first step towards
proving strong collapses, by proving a weaker collapse first.

In answer to Marin's question below: nothing is stronger about inequalities
in the chain of complexiity classes is known yet.  Apart from LogSpace not
equal to Pspace, any of the other classes could be equal.

Sam

.

>
> ---------- Forwarded message ----------
> To: fom at cs.nyu.edu
> Date: Sat, 11 Jul 2015 11:57:13 -0700
> Subject: [FOM] Shipman seeks weaker complexity separations
> In that connection Steve Cook pointed out to me that it is known that
> LogSPACE is known to be a proper subset of PSPACE. Hence in the chain from
> LogSPACE to P to NP to the rungs of the poly-time hierarchy to PSPACE, at
> least one inclusion must be proper.
>
> That was some years ago. Anything at all stronger known today?
>
> Martin
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20150712/b2b251af/attachment-0001.html>