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?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ 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 $\endgroup$– vznOct 8, 2013 at 15:00
-
1$\begingroup$ see also separating L/P & kintalis blog post cited there $\endgroup$– vznOct 8, 2013 at 15:35
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
15
Mulmuley's result (from Mulmuley's webpage 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.
answered Oct 8, 2013 at 14:10
-
$\begingroup$ 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? $\endgroup$– TurboOct 8, 2013 at 17:20
-
$\begingroup$ (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)$. $\endgroup$ Oct 8, 2013 at 17:59
-
$\begingroup$ 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? $\endgroup$– TurboOct 8, 2013 at 18:11
-
$\begingroup$ @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... $\endgroup$ Oct 8, 2013 at 18:34
-
1$\begingroup$ @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. $\endgroup$ Oct 8, 2013 at 19:50
$\begingroup$
$\endgroup$
1
There is a series of works by M. Hofmann and U. Schöpp 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.
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.
answered Oct 9, 2013 at 8:05
-
5$\begingroup$ 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 satisfiability 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... $\endgroup$ Oct 10, 2013 at 2:56
$\begingroup$
$\endgroup$
2
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.
-
3$\begingroup$ FO + LFP without ordering can surely not capture $\mathsf{L}$, by the very reason you quote: it cannot count, not even modulo 2. $\endgroup$ Nov 21, 2014 at 9:02
-
$\begingroup$ Agree. Then the question (or rather, one of the questions) is -- Is FO+LFP (without ord) a strict subset of FO+LFP (with ord)? $\endgroup$ Nov 22, 2014 at 8:44
$\begingroup$
$\endgroup$
This is not really an answer, but as described here 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.
