On Polynomial Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets

Mitsunori Ogiwara Osamu Watanabe

Published in: STOC (1990)

Keyphrases

truth table
boolean functions
computational complexity
defeasible logic
np hard
knowledge base
decision trees
lower bound
np complete
dnf formulas