5
$\begingroup$

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

Improve this question
$\endgroup$
11
  • 5
    $\begingroup$ Wait, what ? P-complete "requires" polynomial space ? since when ? $\endgroup$
    – Suresh Venkat
    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$
    – András Salamon
    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$
    – Tyson Williams
    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$
    – Joshua Grochow
    Apr 25, 2014 at 15:17

0

Reset to default

Your Answer

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