Lance Fortnow recently claimed that proving L != NP should be easier than proving P != NP:Separate NP from Logarithmic space. I gave four approaches in a pre-blog 2001 survey on diagonalization (Section 3) though none have panned out. Should be much easier than separating P from NP.Section 3 in the linked survey claims that there are no meaningful oracle collapse results:While the P != NP question remains quite formidable, the L != NP question seems much more tractable. We have no reason to think this question is difficult. The lack of good relativization models for space means we have no meaningful oracle model where L and NP collapse. Also since L is a uniform class, the Razborov-Rudich [RR97] limitations do not apply.A question about known relativization barriers to L != NP on this site got an answer pointing out that the PSPACE-complete problem TQBF can be used as oracle to get such a collapse. An objection about whether this was a meaningful oracle model seems to be answered too.But even if I would understand why we have no meaningful oracle model where L and NP collapse should be considered to be a correct statement, I would still have my doubts whether proving L != NP is any more feasible than proving P != NP. If proving L != NP should really be easier than proving P != NP, then proving ALogTime != PH should definitively be within reach. (The survey article hints at the possibility to separate $\Sigma_2^p$ from $L$.) I guess ALogTime != PH is still open, and I would like to know whether there are good reasons to expect that it will be hard to prove.
Is ALogTime != PH hard to prove (and unknown)?
cc.complexity theory;reductions;relativization
Not sure why Fortnow says there's no meaningful model where $L$ and $NP$ collapse... it seems to me that QBF should make them collapse, under the usual Ruzzo-Simon-Tompa oracle model (and the link you included agrees). Note this oracle model also has its quirks: we have $L = NL$ if and only if $L^A = NL^A$ for every oracle $A$, so any oracle witnessing a separation would imply the unrelativized separation.ALogTime = LOGTIME-Uniform $NC1$. So yes, $ALogTime = NP$ is open. There is a relativized notion of uniform $NC1$, and you can collapse $NP$ and $NC1$ under that notion. See Theorem 6 in http://link.springer.com/article/10.1007/BF01692056. (A caveat: technically speaking, that paper considers LOGSPACE-uniform NC1, but I believe some reasonable version of that oracle construction should work in the LOGTIME-uniform setting.)Beyond that, I know of no particular reason to believe it is hard to prove other than the observation that many people have tried and none have succeeded yet.