5

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.)

Super8
  • 324
  • 2
  • 8
  • 5
    Wait, what ? P-complete "requires" polynomial space ? since when ? – Suresh Venkat Apr 25 '14 at 12:53
  • 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 Apr 25 '14 at 12:58
  • 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 Apr 25 '14 at 13:01
  • 1
    Perhaps a better phrasing is "assuming P $\ne$ L, ..."? – András Salamon Apr 25 '14 at 13:11
  • The proviso $n^{o(1)}$ implies a stronger space lower bound. $P \ne L$ would have been plausible – Suresh Venkat Apr 25 '14 at 13:18
  • @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 Apr 25 '14 at 13:19
  • 1
    Even if $P \ne L$, it might be that P-complete problems can be solved in sub-polynomial space. – Tyson Williams Apr 25 '14 at 13:20
  • Check out generalizations of Ladner's theorem: http://cstheory.stackexchange.com/a/863/4896. – Sasho Nikolov Apr 25 '14 at 13:52
  • 2
    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 Apr 25 '14 at 15:17
  • re 1st sentence actually efficient parallel time is denoted by the NC class and its open how it relates to other classes – vzn Apr 27 '14 at 02:10
  • 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 Apr 28 '14 at 20:44

0 Answers0