Home » Keyword index

Computational Complexity


Logic » Finite Model Theory

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

Posted by myvardi
updated May 18th, 2012
add new comment
Topology

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

Author(s): Gordon

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?

Keywords: 2-knot; Computational Complexity; knot theory

Posted by rybu
updated July 23rd, 2010
add new comment
Theoretical Comp. Sci. » Algorithms

P vs. NP ★★★★

Author(s): Cook; Levin

Problem   Is P = NP?

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

Posted by zitterbewegung
updated October 18th, 2007
add new comment
Syndicate content