-DNF Resolution on Random CNF Formulas via Expansion.

Anastasia Sofronova Dmitry Sokolov

Published in: Electron. Colloquium Comput. Complex. (2022)

Keyphrases

cnf formula
learning theory
np complete
uniform distribution
learning algorithm
boolean functions
max sat
boolean formula
search space
upper bound
membership queries
pac learning
conjunctive normal form
classification noise