13
$\begingroup$

Lance Fortnow recently claimed that proving L != NP should be easier than proving P != NP:

  1. 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.

Improve this question
$\endgroup$
1
  • $\begingroup$ Lance Fortnow 7:03 AM, May 13, 2016: "Let me rephrase my point. Let AP be alternating polytime (known to be PSPACE unrelativized and thus different from L). Then there is no known relativization model that both makes L = NP for some oracle but separates L from AP for all oracles." $\endgroup$
    – Thomas Klimpel
    Commented May 13, 2016 at 16:21

2 Answers 2

Reset to default
16
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Slightly unrelated: Could you elaborate a bit on the statement: "$L = NL$ iff $L^A = NL^A$ for every $A$"? I don't get the statement in the question to the effect that "the barrier does not apply since $L$ is a uniform class", in fact. Thanks! $\endgroup$
    – Michaël Cadilhac
    Commented May 9, 2016 at 9:52
  • 1
    $\begingroup$ I believe there's a proof of the statement in the paper I linked. Regarding your second sentence: are you asking about why Fortnow says Razborov-Rudich doesn't apply? If so, his point is that the natural proofs barrier as commonly understood only applies if the model you're lower bounding against is non-uniform, e.g. P/poly. $\endgroup$
    – Ryan Williams
    Commented May 10, 2016 at 8:28
  • $\begingroup$ Ah, I misread: I thought that the barrier that did not apply was relativization, not natural proofs, sorry. What I meant to ask was: why is relativization a barrier for P vs NP but not L vs NL, morally? (Hence the unrelatedness of the question.) $\endgroup$
    – Michaël Cadilhac
    Commented May 10, 2016 at 9:10
  • $\begingroup$ In short, it's because the RST oracle model doesn't let you make nondeterministic steps unless the oracle tape is blank. (The reasons for that are subtle; basically some results won't relativize without it.) The actual argument is more complicated... $\endgroup$
    – Ryan Williams
    Commented May 10, 2016 at 20:58
2
$\begingroup$

A naive idea for proving ALogTime != PH: The Boolean formula value problem is complete for ALogTime under deterministic log time reductions. Hence if ALogTime = PH, then PH = coNP = ALogTime, and hence the Boolean formula value problem would be complete under deterministic log time reductions for coNP. Hence there would be a deterministic log time reduction from the tautology problem to the Boolean formula value problem.

The deterministic log time reductions should be harmless, they cannot contribute much to the solution of the tautology problem. They are just a nice formalisation what it means that a reduction can only work very locally. Hence the remaining task is to understand why the tautology problem cannot be turned into a Boolean formula value problem by very local reductions. I still don't see how to do that, but at least the remaining task is very clear, so that I have at least a chance to understand why it is hard (or not).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.