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.)
Stronger versions of P != NP which better express actual convictions
complexity theory;np complete;p vs np