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

  • 5
    $\begingroup$ Wait, what ? P-complete "requires" polynomial space ? since when ? $\endgroup$ Apr 25, 2014 at 12:53
  • $\begingroup$ 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. $\endgroup$
    – Super8
    Apr 25, 2014 at 12:58
  • 1
    $\begingroup$ Perhaps a better phrasing is "assuming P $\ne$ L, ..."? $\endgroup$ Apr 25, 2014 at 13:11
  • 1
    $\begingroup$ Even if $P \ne L$, it might be that P-complete problems can be solved in sub-polynomial space. $\endgroup$ Apr 25, 2014 at 13:20
  • 2
    $\begingroup$ 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... $\endgroup$ Apr 25, 2014 at 15:17


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.