login/create account
P
P vs. PSPACE ★★★
Author(s): Folklore
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?
Keywords: P; PSPACE; separation; unconditional
P vs. NP ★★★★
Problem Is P = NP?
Keywords: Complexity Class; Computational Complexity; Millenium Problems; NP; P; polynomial algorithm
Drupal
CSI of Charles University