<p><a href="http://dx.doi.org/10.1137/S0097539794282930" rel="nofollow">Mulmuley's result</a> (from <a href="http://gct.cs.uchicago.edu/lower-bound.ps" rel="nofollow">Mulmuley's webpage</a> without paywall) that, in the PRAM model without bit operations, "$\mathsf{P} \neq \mathsf{NC}$". (In the usual boolean model where $\mathsf{L}$ lives, $\mathsf{L} \subseteq \mathsf{NC}$.) This model is strong enough that the result implies any $\mathsf{L}$ algorithm for a $\mathsf{P}$-complete problem would have to look quite different from most known algorithms for $\mathsf{P}$-complete problems.</p>

<p>The PRAM model without bit operations is a nonuniform, algebraic model over $\mathbb{Z}$ (similar to algebraic computation trees or the Blum--Shub--Smale algebraic RAM model) in which the nonuniform program can depend not just on the number of integer inputs, but also on their total bitlength. In this way it's not a "purely" algebraic model, but lives somewhere between algebraic and boolean. This model includes poly-time algorithms for linear programming, maxflow, mincut, weighted spanning tree, shortest paths, and other combinatorial optimization problems, the logspace algorithm for tree isomorphism (see comments below), and algorithms for approximating the complex roots of polynomials, which is why I say any $\mathsf{L}$ algorithm for a $\mathsf{P}$-complete problem (which, as your question indicates you know, most people think does not exist) would have to look quite different from any of these.</p>

CC BY-SA 3.0
2013-10-08T17:20:31.713Z
In his conjecture on page 62, how does Mulmuley related $SL_m(C)$ with mincost-flow? Why does $L$ have to be linear and $F$ a bijection? The conjecture seems to imply no rank-$k$ linear map (since inverse map of a linear 1−1 map is linear) evaluated on zero set of $SL_m(C)$ can cover $L(n)$. Is my interpretation correct?
Turbo
CC BY-SA 3.0
2013-10-08T17:59:30.927Z
(Good question, but seems somewhat orthogonal to the question being asked here...) Yes. Anything computable efficiently in the PRAM model without bit operations has a small formula $\varphi$, hence (by Valiant) is a projection of det: $\varphi(x) = \det(F(x))$. In particular, $x \in L(n)$ iff $\det(F(x)) = 1$ iff $x \in F^{-1}(SL_m)$.
Joshua Grochow
CC BY-SA 3.0
2013-10-08T18:11:07.177Z
the only assumption is $det\notin NC^{1}$ which seems to be the case. Pretty Interesting! As with any other such complexity assumotions and proofs - Is the other way known: that is if $det\in NC^1$, is $P=NC$? I have never seen such converses in complexity theory or is such converses not possible?
Turbo
CC BY-SA 3.0
2013-10-08T18:34:29.637Z
@JAS: I don't see what you mean by "the only assumption is...": I don't think it follows that $\det \notin NC^1 \Rightarrow P \neq NC$, if that's what you were saying...
Joshua Grochow
CC BY-SA 3.0
2013-10-08T19:40:20.610Z
No, in the paper, further on, $\det\notin NC^1$ is shown enough to support the conjecture. this is what I mean.
Turbo
CC BY-SA 3.0
2013-10-08T19:50:35.473Z
@JAS: The belief that $det \notin NC^1$ *supports* the conjecture, but it doesn't *imply* the conjecture. He mentions the converse, that if perfect matching $\in NC^1$ then the conjecture is false for small $a$. Equivalently, if the conjecture is true then perfect matching $\notin NC^1$. Note that this is the opposite direction of what you were saying.
Joshua Grochow
CC BY-SA 3.0
2013-10-08T20:00:59.007Z
yes thankyou very much
Turbo
CC BY-SA 3.0
2014-04-03T16:35:24.280Z
@Ricky: Yes, it is efficiently decidable in that model. For a problem that only has boolean parameters and not numerical ones, the PRAM model without bit operations is the same as the usual PRAM model, which may be why problems such as Tree Iso aren't mentioned in the paper...
Joshua Grochow
CC BY-SA 3.0
2014-04-03T17:50:37.653Z
@Ricky: I was thinking of adjacency matrix, but okay. Even for adjacency list, I haven't checked closely, but I believe the L algorithms for Tree Iso (e.g. Lindell, STOC 1992) work within the PRAM model without bit operations. That is, they treat the vertex labels as integers, but they only use <, = on these numbers, together with combinatorial operations on the structure of the tree.
Joshua Grochow
CC BY-SA 3.0
2018-04-27T05:21:14.763Z
@JoshuaGrochow Is $P\neq NC$ in PRAM model (that Mulmuley apparently proves separation in) same as $P\neq NC$ in BSS model? That is does this $P\neq NC$ result give $P\neq NC$ in BSS model?
Turbo
CC BY-SA 3.0
2018-04-27T05:39:55.450Z
@JoshuaGrochow We know $P_\mathbb R\neq NC_\mathbb R$ holds from FELIPE CUCKER's result and we know $P\neq NC$ in PRAM model. At least do they imply $P_R\neq NC_R$ for BSS model for any ring $R$?
Turbo
CC BY-SA 3.0
2018-04-27T12:27:47.510Z
@Turbo: surely not. Both of those results are essentially in characteristic zero. If what you say held over F_2 it would be true for the Boolean classes.
Joshua Grochow
CC BY-SA 3.0
2018-04-27T12:44:45.903Z
@JoshuaGrochow Thank you. I see then what more would it take to prove $P_R\neq NC_R$ in BSS model for any ring $R$ and that model looks very close to PRAM model (no bit access etc.) and it looks like a separation in BSS is long overdue? It looks like that still would be a much weaker than $P\neq NC$ in Turing.
Turbo
CC BY-SA 3.0
2013-10-08T14:10:34.687Z
2014-04-04T16:55:14.050Z
2014-04-04T16:55:14.050Z
Joshua Grochow
<p>There is a series of works by <a href="http://www.tcs.ifi.lmu.de/people/martin-hofmann">M. Hofmann</a> and <a href="http://www.tcs.ifi.lmu.de/people/ulrich-schoepp">U. Schöpp</a> that formalizes the intuitive notion of "typical logarithmic space algorithms", using only a constant number of pointers to the input data structure, as a programming language PURPLE (pure pointer programs with iteration.)</p>

<p>Even though PURPLE programs do not capture all of $\mathsf{L}$ (they have been shown to be unable to decide undirected s-t-connectiviy), their extension with counting is shown to capture a large fraction of $\mathsf{L}$, but not the P-complete problem Horn-SAT. 
This is shown in the latest paper in the series: 
<a href="http://link.springer.com/chapter/10.1007/978-3-642-37075-5_21">M. Hofmann, R. Ramyaa and U. Schöpp: Pure Pointer Programs and Tree Isomorphism, FOSSACS 2013.</a></p>

<p>The conclusion seems to be that logarithmic space algorithms for $\mathsf{P}$-complete problems must be very untypical and go beyond what can be implemented in PURPLE with counting.</p>

CC BY-SA 3.0
2013-10-10T02:56:46.220Z
PURPLE with counting is an interesting model, and corresponds to my naive intuition of logspace algorithms. But I don't know if this result is good evidence for $L \neq P$: they even say "So, Horn satisﬁability cannot be decided in PURPLE augmented with nondeterminism and counting either, but for the very reason that a particular LOGSPACE problem, namely tree isomorphism cannot." This essentially says that the result is really about the weakness of PURPLE+count (corresponding to the naive intuition of logspace algos) rather than the weakness of L...
Joshua Grochow
CC BY-SA 3.0
2013-10-09T08:05:56.000Z
2014-04-03T08:42:29.990Z
2014-04-03T08:42:29.990Z
Jan Johannsen
<p>Descriptive complexity has attempted to provide some answers.</p>

<p>FO (first order logic), with <em>ord</em> (ordering of the domain ) and TC (transitive closure) $= L$.</p>

<p>FO + ord + LFP (least fixed point) $= P$.</p>

<p>So the question arises -- Is FO+ord+TC $\subset$ FO+ord+LFP?</p>

<p>On the other hand, FO + LFP (without ord) cannot even count!  For example, it is unable express the fact that the cardinality of the domain is even.  This logic certainly cannot capture $P$ -- but the question is, can it capture $L$ or $NL$?</p>

<p>See for example <a href="http://www.cs.umass.edu/%7Eimmerman/pub/EATCScolumn.pdf" rel="nofollow">http://www.cs.umass.edu/%7Eimmerman/pub/EATCScolumn.pdf</a></p>

<p>And then, second-order (SO) + Horn logic captures P, whereas SO+Krom captures NL.
See Erich Gradel, <em>Capturing complexity classes by fragments of second-order logic</em>, Theoretical Computer Science, 1992.</p>

CC BY-SA 3.0
2014-11-21T09:02:48.707Z
FO + LFP without ordering can surely not capture $\mathsf{L}$, by the very reason you quote: it cannot count, not even modulo 2.
Jan Johannsen
CC BY-SA 3.0
2014-11-22T08:44:35.340Z
Agree.  Then the question (or rather, *one* of the questions) is -- Is FO+LFP (without ord) a strict subset of FO+LFP (with ord)?
Martin Seymour
CC BY-SA 3.0
2014-11-21T06:28:00.650Z
2014-11-21T06:28:00.650Z
Martin Seymour
<p>This is not really an answer, but as described <a href="https://cstheory.stackexchange.com/questions/21631/notion-of-associativity-for-ternary-relations">here</a> I believe that for the $\sf{P}$-complete problem $\sf{GEN}$ it should be possible to define some "complexity measure" on the instances such that solving an instance of complexity $k$ would require $\Theta(k \log n)$ space. If true this would imply the desired separation; if we identify such a measure, it seems within reach to bound the <em>monotone</em> space complexity of the instances, and this would give tangible evidence that we're on the right track - although showing a non-monotone bound is apparently much harder.</p>

CC BY-SA 3.0
2014-04-04T02:11:00.673Z
2014-04-04T02:11:00.673Z
2017-04-13T12:32:28.743Z
NisaiVloot
<p>What are the compelling reasons for believing $L\neq P$? L is the class of log-space algorithms with pointers to the input.</p>

<p>Suppose L=P for the moment. What would a log-space algorithm for a P-complete problem look like in its general outlines?</p>

CC BY-SA 3.0
2013-10-08T15:00:08.230Z
in a sense it would be a space compression algorithm for a P-time Turing machine computation which usually takes P space. hence if L≠P then there is some "(in)compressibility limit" of P. a possible construction/question/research direction based on this angle, [compression of TM run sequence](http://mathoverflow.net/questions/86339/compression-of-a-turing-machine-run-sequence)
vzn
CC BY-SA 3.0
2013-10-08T15:35:39.670Z
see also [separating L/P](http://cstheory.stackexchange.com/questions/1775/separating-logspace-from-polynomial-time) & kintalis [blog post](http://kintali.wordpress.com/2010/02/04/logspace-vs-polynomial-time/) cited there
vzn
<cc.complexity-theory><complexity-classes>
What are the compelling reasons for believing $L\neq P$?
Jumer
# What are the compelling reasons for believing $L\neq P$?

(Asked by: username_0 on 2013-10-08)

What are the compelling reasons for believing $L\neq P$? L is the class of log-space algorithms with pointers to the input.

Suppose L=P for the moment. What would a log-space algorithm for a P-complete problem look like in its general outlines?

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: in a sense it would be a space compression algorithm for a P-time Turing machine computation which usually takes P space. hence if L≠P then there is some "(in)compressibility limit" of P. a possible construction/question/research direction based on this angle, [compression of TM run sequence](http://mathoverflow.net/questions/86339/compression-of-a-turing-machine-run-sequence)  
> **username_1**: see also [separating L/P](http://cstheory.stackexchange.com/questions/1775/separating-logspace-from-polynomial-time) & kintalis [blog post](http://kintali.wordpress.com/2010/02/04/logspace-vs-polynomial-time/) cited there  

---

## 4 answers

### Answer by username_2 on 2013-10-08. Score: 28

[Mulmuley's result](http://dx.doi.org/10.1137/S0097539794282930) (from [Mulmuley's webpage](http://gct.cs.uchicago.edu/lower-bound.ps) without paywall) that, in the PRAM model without bit operations, "$\mathsf{P} \neq \mathsf{NC}$". (In the usual boolean model where $\mathsf{L}$ lives, $\mathsf{L} \subseteq \mathsf{NC}$.) This model is strong enough that the result implies any $\mathsf{L}$ algorithm for a $\mathsf{P}$-complete problem would have to look quite different from most known algorithms for $\mathsf{P}$-complete problems.

The PRAM model without bit operations is a nonuniform, algebraic model over $\mathbb{Z}$ (similar to algebraic computation trees or the Blum--Shub--Smale algebraic RAM model) in which the nonuniform program can depend not just on the number of integer inputs, but also on their total bitlength. In this way it's not a "purely" algebraic model, but lives somewhere between algebraic and boolean. This model includes poly-time algorithms for linear programming, maxflow, mincut, weighted spanning tree, shortest paths, and other combinatorial optimization problems, the logspace algorithm for tree isomorphism (see comments below), and algorithms for approximating the complex roots of polynomials, which is why I say any $\mathsf{L}$ algorithm for a $\mathsf{P}$-complete problem (which, as your question indicates you know, most people think does not exist) would have to look quite different from any of these.

> **Comments:**
> **username_3**: In his conjecture on page 62, how does Mulmuley related $SL_m(C)$ with mincost-flow? Why does $L$ have to be linear and $F$ a bijection? The conjecture seems to imply no rank-$k$ linear map (since inverse map of a linear 1−1 map is linear) evaluated on zero set of $SL_m(C)$ can cover $L(n)$. Is my interpretation correct?  
> **username_2**: (Good question, but seems somewhat orthogonal to the question being asked here...) Yes. Anything computable efficiently in the PRAM model without bit operations has a small formula $\varphi$, hence (by Valiant) is a projection of det: $\varphi(x) = \det(F(x))$. In particular, $x \in L(n)$ iff $\det(F(x)) = 1$ iff $x \in F^{-1}(SL_m)$.  
> **username_3**: the only assumption is $det\notin NC^{1}$ which seems to be the case. Pretty Interesting! As with any other such complexity assumotions and proofs - Is the other way known: that is if $det\in NC^1$, is $P=NC$? I have never seen such converses in complexity theory or is such converses not possible?  
> **username_2**: @JAS: I don't see what you mean by "the only assumption is...": I don't think it follows that $\det \notin NC^1 \Rightarrow P \neq NC$, if that's what you were saying...  
> **username_3**: No, in the paper, further on, $\det\notin NC^1$ is shown enough to support the conjecture. this is what I mean.  
> **username_2**: @JAS: The belief that $det \notin NC^1$ *supports* the conjecture, but it doesn't *imply* the conjecture. He mentions the converse, that if perfect matching $\in NC^1$ then the conjecture is false for small $a$. Equivalently, if the conjecture is true then perfect matching $\notin NC^1$. Note that this is the opposite direction of what you were saying.  
> **username_3**: yes thankyou very much  
> **username_2**: @Ricky: Yes, it is efficiently decidable in that model. For a problem that only has boolean parameters and not numerical ones, the PRAM model without bit operations is the same as the usual PRAM model, which may be why problems such as Tree Iso aren't mentioned in the paper...  
> **username_2**: @Ricky: I was thinking of adjacency matrix, but okay. Even for adjacency list, I haven't checked closely, but I believe the L algorithms for Tree Iso (e.g. Lindell, STOC 1992) work within the PRAM model without bit operations. That is, they treat the vertex labels as integers, but they only use <, = on these numbers, together with combinatorial operations on the structure of the tree.  
> **username_3**: @JoshuaGrochow Is $P\neq NC$ in PRAM model (that Mulmuley apparently proves separation in) same as $P\neq NC$ in BSS model? That is does this $P\neq NC$ result give $P\neq NC$ in BSS model?  
> **username_3**: @JoshuaGrochow We know $P_\mathbb R\neq NC_\mathbb R$ holds from FELIPE CUCKER's result and we know $P\neq NC$ in PRAM model. At least do they imply $P_R\neq NC_R$ for BSS model for any ring $R$?  
> **username_2**: @Turbo: surely not. Both of those results are essentially in characteristic zero. If what you say held over F_2 it would be true for the Boolean classes.  
> **username_3**: @JoshuaGrochow Thank you. I see then what more would it take to prove $P_R\neq NC_R$ in BSS model for any ring $R$ and that model looks very close to PRAM model (no bit access etc.) and it looks like a separation in BSS is long overdue? It looks like that still would be a much weaker than $P\neq NC$ in Turing.  

---

### Answer by username_4 on 2013-10-09. Score: 15

There is a series of works by [M. Hofmann](http://www.tcs.ifi.lmu.de/people/martin-hofmann) and [U. Schöpp](http://www.tcs.ifi.lmu.de/people/ulrich-schoepp) that formalizes the intuitive notion of "typical logarithmic space algorithms", using only a constant number of pointers to the input data structure, as a programming language PURPLE (pure pointer programs with iteration.)

Even though PURPLE programs do not capture all of $\mathsf{L}$ (they have been shown to be unable to decide undirected s-t-connectiviy), their extension with counting is shown to capture a large fraction of $\mathsf{L}$, but not the P-complete problem Horn-SAT.
This is shown in the latest paper in the series:
[M. Hofmann, R. Ramyaa and U. Schöpp: Pure Pointer Programs and Tree Isomorphism, FOSSACS 2013.](http://link.springer.com/chapter/10.1007/978-3-642-37075-5_21)

The conclusion seems to be that logarithmic space algorithms for $\mathsf{P}$-complete problems must be very untypical and go beyond what can be implemented in PURPLE with counting.

> **Comments:**
> **username_2**: PURPLE with counting is an interesting model, and corresponds to my naive intuition of logspace algorithms. But I don't know if this result is good evidence for $L \neq P$: they even say "So, Horn satisﬁability cannot be decided in PURPLE augmented with nondeterminism and counting either, but for the very reason that a particular LOGSPACE problem, namely tree isomorphism cannot." This essentially says that the result is really about the weakness of PURPLE+count (corresponding to the naive intuition of logspace algos) rather than the weakness of L...  

---

### Answer by username_5 on 2014-11-21. Score: 3

Descriptive complexity has attempted to provide some answers.

FO (first order logic), with *ord* (ordering of the domain ) and TC (transitive closure) $= L$.

FO + ord + LFP (least fixed point) $= P$.

So the question arises -- Is FO+ord+TC $\subset$ FO+ord+LFP?

On the other hand, FO + LFP (without ord) cannot even count! For example, it is unable express the fact that the cardinality of the domain is even. This logic certainly cannot capture $P$ -- but the question is, can it capture $L$ or $NL$?

See for example <http://www.cs.umass.edu/%7Eimmerman/pub/EATCScolumn.pdf>

And then, second-order (SO) + Horn logic captures P, whereas SO+Krom captures NL.
See Erich Gradel, *Capturing complexity classes by fragments of second-order logic*, Theoretical Computer Science, 1992.

> **Comments:**
> **username_4**: FO + LFP without ordering can surely not capture $\mathsf{L}$, by the very reason you quote: it cannot count, not even modulo 2.  
> **username_5**: Agree.  Then the question (or rather, *one* of the questions) is -- Is FO+LFP (without ord) a strict subset of FO+LFP (with ord)?  

---

### Answer by username_6 on 2014-04-04. Score: 1

This is not really an answer, but as described [here](https://cstheory.stackexchange.com/questions/21631/notion-of-associativity-for-ternary-relations) I believe that for the $\sf{P}$-complete problem $\sf{GEN}$ it should be possible to define some "complexity measure" on the instances such that solving an instance of complexity $k$ would require $\Theta(k \log n)$ space. If true this would imply the desired separation; if we identify such a measure, it seems within reach to bound the *monotone* space complexity of the instances, and this would give tangible evidence that we're on the right track - although showing a non-monotone bound is apparently much harder.


---

