P


P vs. PSPACE ★★★

Author(s): Folklore

\begin{problem} Is there a problem that can be computed by a Turing machine in polynomial space and unbounded time but not in polynomial time? More formally, does P = PSPACE? \end{problem}

Keywords: P; PSPACE; separation; unconditional

P vs. NP ★★★★

Author(s): Cook; Levin

\begin{problem} Is P = NP? \end{problem}

Keywords: Complexity Class; Computational Complexity; Millenium Problems; NP; P; polynomial algorithm

Syndicate content