Does the conviction "L-uniform NC1 != NP is incredibly hard to prove!" express the core of "P != NP is incredibly hard to prove!" in a similar spirit as the conviction "The polynomial hierarchy doesn't collapse!" expresses the core of "P is not equal to NP!" ? Let me try to elaborate:

The P vs NP problem implicitly invokes a number of related but distinct challenges and convictions. Focusing on the convictions, we have that NP != coNP is believed with nearly the same conviction as P != NP, and is part of the conviction that the polynomial hierarchy doesn't collapse. (Because the polynomial hierarchy is less familiar than NP, this conviction is weaker, but still strong enough to be used as a reasonable assumption in a proof.)

Similarly, "L != NP is incredibly hard to prove" is believed with nearly the same conviction as "P != NP is incredibly hard to prove". Now there may be weaker statements which we don't know how to prove either, like "$U_{E^*}$-uniform TC0 != PH", but they don't necessarily feel natural enough to be part of real convictions. So my question is whether "L-uniform NC1 != NP is incredibly hard to prove" would qualify as a natural (and sufficiently strong) conviction. (I'm pretty certain that "NC1" is appropriate here, but I'm less certain about "L-uniform" and "NP". Maybe something like "non-uniform NC1 != PH/poly is incredibly hard to prove" would be much more natural and somehow imply all the other related natural convictions.)

  • $\begingroup$ What is ​ $U_{E_*}$ ? ​ ​ ​ ​ $\endgroup$
    – user12859
    Commented Jan 26, 2016 at 10:52
  • $\begingroup$ @RickyDemer It is from the reference in the answer by Yuval Filmus to a question which is related to my confusion about the appropriate notion of uniformity. The sentence reads: "There is a reasonable though complicated notion of $NC^1$ uniformity ("$U_{E_*}$ uniformity") due to Ruzzo [Ru81] (see also [Co85]) which has the consequence..." The intention of using it in the question is similar to writing $TC^0$ in being a notion that an expert may know, but still being a possibly appropriate one. $\endgroup$ Commented Jan 26, 2016 at 11:41
  • $\begingroup$ I started to spend much time related to this question, and tried to remember why I wanted to ask it: I felt that subset sum was an unusual NP-complete problem (because memcomputing claims that it can solve it), and tried to come up with finer distinctions between NP-complete problems. One idea was that an NP-complete problem might not just be complete wrt P, but also wrt L or even L-uniform $NC^1$. Then I realized that subset sum is unusual for a completely different reason, but decided to ask this question anyway. After all, most reductions are much weaker than P, which also means something. $\endgroup$ Commented Feb 1, 2016 at 22:36

1 Answer 1


Considering that the conviction "P != NP is incredibly hard to prove" is largely based on known barrier results, one promising approach (for answering this question) would be to look for a statement expressing a natural separation, and ask why it is hard to prove. Then one can check which of the known barrier results for P != NP can be extended to that statement.

The question "Why is it hard to prove ALogTime != PH?" should be most promising in this respect. This statement is weaker and more natural than "L-uniform NC1 != NP", because $\subset$ PH and

ALogTime = DLogTime-uniform NC1 = $U_{E^*}$-uniform NC1 $\subset$ L-uniform NC1.

For the relativization barrier, it would be enough to show ALogTimeA = PHA for A := TQBF, where TQBF is the PSPACE-complete problem to decide true quantified Boolean formulas. No idea whether the natural proofs and the algebrizing proofs barrier should be expected to carry over, but at least checking whether they do should not be terribly difficult.

I also wonder whether the statement "ALogTime != PH" points to the right place where the difficulties for proving separation results start. Below ALogTime, we have the logarithmic time hierarchy LH, which probably doesn't collapse either, but the question is whether this has been proved (or whether this is relatively easy to prove, just in case nobody cared yet).

Edit: It turns out somebody actually cared to prove that the logarithmic time hierarchy is strict, and how it is related to the AC0 hierarchy. See Searching Constant Width Mazes Captures the AC0 Hierarchy by Barrington et al. I didn't check which results were already proved in one of the references, and which results have been proved for the first time in that paper.

This means that the statement "ALogTime != PH" is exactly the place where the difficulties for proving separation results start. It may be noted that this statement is actually equivalent to "ALogTime != NP", since "ALogTime = NP" would imply "P=NP=PH". Observe that (it seems that) coNLogTime verification can be used instead of PTime verification when characterising NP, so this is actually really equivalent to a statement where "polynomial time" no longer occurs, only some version of "read only polynomial length witness string".

  • $\begingroup$ The strictness of the non-uniform AC^0 hierarchy was first proved in Sipser, M. Borel sets and circuit complexity. STOC 1983. The cited by Barrington et all 1997 establishes the same result for the uniform AC^0 hierarchy, which corresponds to the logarithmic time hierarchy. $\endgroup$ Commented Nov 9, 2016 at 10:04

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.