[FOM] Shipman seeks weaker complexity separations

roux cody cody.roux at gmail.com
Sat Jul 11 23:12:50 EDT 2015

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

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




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>

More information about the FOM mailing list