New Collapse Consequences of NP Having Small Circuits.

Johannes Köbler Osamu Watanabe

Published in: SIAM J. Comput. (1998)

Keyphrases

computational complexity
truth table
information retrieval
decision making
small number
digital circuits
database
computer vision
data structure
np complete
small size
medium size