# Computational Complexity

## Complexity of QBF(Bounded Treewidth) ★★

Author(s): Moshe Y. Vardi

**Question**What is the computational complexity of QBF(Bounded Treewidth)? Is it PSPACE-complete? In PTIME?

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

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

Author(s): Gordon

**Problem**Does there exist a smooth/PL embedding of in such that the fundamental group of the complement has an unsolvable word problem?

Keywords: 2-knot; Computational Complexity; knot theory

## P vs. NP ★★★★

**Problem**Is P = NP?

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