Computational Complexity

Complexity of QBF(Bounded Treewidth) ★★

Author(s): Moshe Y. Vardi

\begin{question} What is the computational complexity of QBF(Bounded Treewidth)? Is it PSPACE-complete? In PTIME? \end{question}

Keywords: bounded tree width; Computational Complexity; FMT12-LesHouches; QBF

Unsolvability of word problem for 2-knot complements ★★★

Author(s): Gordon

\begin{problem} Does there exist a smooth/PL embedding of $S^2$ in $S^4$ such that the fundamental group of the complement has an unsolvable word problem? \end{problem}

Keywords: 2-knot; Computational Complexity; knot theory

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