If NP has Polynomial-Size Circuits, then MA=AM.

Vikraman Arvind Johannes Köbler Uwe Schöning Rainer Schuler

Published in: Theor. Comput. Sci. (1995)

Keyphrases

polynomial size
exponential size
np complete
boolean functions
dnf formulas
bounded treewidth
knowledge compilation
computational complexity
np hard
heuristic search
uniform distribution
machine learning
special case
data management