[FOM] Shipman seeks weaker complexity separations

[roux cody]

Dear Martin,

I'm afraid if you are referring to the hierarchy LOGSPACE < NC < P < NP <
PSPACE, none of the inclusions are known to be strict (to the best of my
knowledge).

The complexity zoo is pretty up to date with current knowledge about these
questions:

https://complexityzoo.uwaterloo.ca/Complexity_Zoo


Best,

Cody

On Sat, Jul 11, 2015 at 2:57 PM, Martin Davis <martin at eipye.com> wrote:

> 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/20150711/61a2c583/attachment.html>