Separating Polynomial-Time Turing and Truth-Table Reductions by Tally Sets.

Shouwen Tang Ronald V. Book

Published in: ICALP (1988)

Keyphrases

truth table
boolean functions
defeasible logic
dnf formulas
special case
machine learning
log log
approximation algorithms
concept learning
uniform distribution
membership queries
bounded treewidth