<p>It is admitted that a $\mathsf{P}$-complete problem requires polynomial space and thus cannot be efficiently parallelized. One purpose of these problems is that they can be used to 'defeat' an (untrustworthy?) adversary with massively parallel computing abilities (e.g. cluster computing) : assuming that we have access to a sequential computer with higher clockrate than the adversary's, we may hope to solve a $\mathsf{P}$-complete problem faster than him due to its intrinsic sequentiality.</p>

<p>However, there are some polynomial problems which precise space complexity is unknown. Prominent examples come from computational biology problems, with typical examples being the sequence and tree alignment problems (such as LCS/MAST which are usually solved by dynamic programming). While not believed to be $\mathsf{P}$-complete, the only 'speedups' known for these problems use variants of DP (such as <em>sparse dynamic programming</em>) and do not lend themselves to parallelisation.</p>

<p>Whence the following question: is there any <em>theoretical</em> evidence of polynomial problems outside of ($\mathsf{P-complete} \cup Dspace(n^{o(1)})$)?</p>

<p>(NOTE ADDED: I suspect that the above mentioned problems are in $NC_2$, so they're not a good illustration of my point; I'll look for other examples.)</p>

CC BY-SA 3.0
2014-04-25T12:53:20.980Z
Wait, what ? P-complete "requires" polynomial space ? since when ?
Suresh Venkat
CC BY-SA 3.0
2014-04-25T12:58:37.373Z
This seems a reasonable assumption given the current state of knowledge. E.g. for the $\mathsf{P}$-complete problem *CircuitEval*, it doesn't seem possible to do better than a bottom-up evaluation with memorization. I understand that a formal proof of this statement is currently considered out of reach, although I'm not an expert in CC.
Super8
CC BY-SA 3.0
2014-04-25T13:01:12.700Z
I don't think there's anything reasonable (or standard) about a claim that P-complete problems "require" poly space. Unless I misunderstand and by "poly" you merely mean "linear or better" ?
Suresh Venkat
CC BY-SA 3.0
2014-04-25T13:11:54.287Z
Perhaps a better phrasing is "assuming P $\ne$ L, ..."?
András Salamon
CC BY-SA 3.0
2014-04-25T13:18:39.377Z
The proviso $n^{o(1)}$ implies a stronger space lower bound. $P \ne L$ would have been plausible
Suresh Venkat
CC BY-SA 3.0
2014-04-25T13:19:52.493Z
@AndrásSalamon: I'm not sure, maybe the correct assumption would be $P \neq NC$? My understanding is that if a problem is in $DSPACE(f(n))$, then it can be solved by circuits of height $f(n)$ and thus can be solved in time $f(n)$ using $2^{f(n)}$ parallel processors. Please correct me if I'm wrong.
Super8
CC BY-SA 3.0
2014-04-25T13:20:05.050Z
Even if $P \ne L$, it might be that P-complete problems can be solved in sub-polynomial space.
Tyson Williams
CC BY-SA 3.0
2014-04-25T13:52:03.943Z
Check out generalizations of Ladner's theorem: http://cstheory.stackexchange.com/a/863/4896.
Sasho Nikolov
CC BY-SA 3.0
2014-04-25T15:17:43.633Z
Putting together what's been hinted at in the previous comments: assuming $\mathsf{P} \not\subseteq \mathsf{SPACE}(n^{o(1)})$, then generalized Ladner implies there are (infinitely many distinct equivalence classes of) problems in $\mathsf{P}$ that are neither $\mathsf{P}$-complete nor in $\mathsf{SPACE}(n^{o(1)})$. The question of the complexity (in terms of space and in terms of $\mathsf{P}$-completeness) of the computational biology problems you mentioned seems like a pretty interesting question on its own...
Joshua Grochow
CC BY-SA 3.0
2014-04-27T02:10:38.857Z
re 1st sentence actually efficient parallel time is denoted by the [NC class](http://en.wikipedia.org/wiki/NC_(complexity)) and its open how it relates to other classes
vzn
CC BY-SA 3.0
2014-04-28T20:44:55.643Z
This question is confusing for a variety of reasons, but perhaps you might be interested in polylogarithmic space instead of sub-polynomial space, and the relationship between P, polyL, and SC. The class polyL is polylogarithmic space. The class SC is the class of languages decidable by an algorithm that _simultaneously_ uses polynomial time and polylogarithmic space. SC is a subset of both P and polyL. P and polyL are not equal, but we don't know if one is a strict subset of the other or if they are incomparable.
argentpepper
<cc.complexity-theory><dc.parallel-comp><dynamic-programming>
Evidence of non P-hard problems that require polynomial space?
Super8
# Evidence of non P-hard problems that require polynomial space?

(Asked by: username_0 on 2014-04-25)

It is admitted that a $\mathsf{P}$-complete problem requires polynomial space and thus cannot be efficiently parallelized. One purpose of these problems is that they can be used to 'defeat' an (untrustworthy?) adversary with massively parallel computing abilities (e.g. cluster computing) : assuming that we have access to a sequential computer with higher clockrate than the adversary's, we may hope to solve a $\mathsf{P}$-complete problem faster than him due to its intrinsic sequentiality.

However, there are some polynomial problems which precise space complexity is unknown. Prominent examples come from computational biology problems, with typical examples being the sequence and tree alignment problems (such as LCS/MAST which are usually solved by dynamic programming). While not believed to be $\mathsf{P}$-complete, the only 'speedups' known for these problems use variants of DP (such as *sparse dynamic programming*) and do not lend themselves to parallelisation.

Whence the following question: is there any *theoretical* evidence of polynomial problems outside of ($\mathsf{P-complete} \cup Dspace(n^{o(1)})$)?

(NOTE ADDED: I suspect that the above mentioned problems are in $NC\_2$, so they're not a good illustration of my point; I'll look for other examples.)

**Tags:** cc.complexity-theory, dc.parallel-comp, dynamic-programming

> **Comments:**
> **username_1**: Wait, what ? P-complete "requires" polynomial space ? since when ?  
> **username_0**: This seems a reasonable assumption given the current state of knowledge. E.g. for the $\mathsf{P}$-complete problem *CircuitEval*, it doesn't seem possible to do better than a bottom-up evaluation with memorization. I understand that a formal proof of this statement is currently considered out of reach, although I'm not an expert in CC.  
> **username_1**: I don't think there's anything reasonable (or standard) about a claim that P-complete problems "require" poly space. Unless I misunderstand and by "poly" you merely mean "linear or better" ?  
> **username_2**: Perhaps a better phrasing is "assuming P $\ne$ L, ..."?  
> **username_1**: The proviso $n^{o(1)}$ implies a stronger space lower bound. $P \ne L$ would have been plausible  
> **username_0**: @AndrásSalamon: I'm not sure, maybe the correct assumption would be $P \neq NC$? My understanding is that if a problem is in $DSPACE(f(n))$, then it can be solved by circuits of height $f(n)$ and thus can be solved in time $f(n)$ using $2^{f(n)}$ parallel processors. Please correct me if I'm wrong.  
> **username_3**: Even if $P \ne L$, it might be that P-complete problems can be solved in sub-polynomial space.  
> **username_4**: Check out generalizations of Ladner's theorem: http://cstheory.stackexchange.com/a/863/4896.  
> **username_5**: Putting together what's been hinted at in the previous comments: assuming $\mathsf{P} \not\subseteq \mathsf{SPACE}(n^{o(1)})$, then generalized Ladner implies there are (infinitely many distinct equivalence classes of) problems in $\mathsf{P}$ that are neither $\mathsf{P}$-complete nor in $\mathsf{SPACE}(n^{o(1)})$. The question of the complexity (in terms of space and in terms of $\mathsf{P}$-completeness) of the computational biology problems you mentioned seems like a pretty interesting question on its own...  
> **username_6**: re 1st sentence actually efficient parallel time is denoted by the [NC class](http://en.wikipedia.org/wiki/NC_(complexity)) and its open how it relates to other classes  
> **username_7**: This question is confusing for a variety of reasons, but perhaps you might be interested in polylogarithmic space instead of sub-polynomial space, and the relationship between P, polyL, and SC. The class polyL is polylogarithmic space. The class SC is the class of languages decidable by an algorithm that _simultaneously_ uses polynomial time and polylogarithmic space. SC is a subset of both P and polyL. P and polyL are not equal, but we don't know if one is a strict subset of the other or if they are incomparable.  

---

## 0 answers

