КТИ-2016: Symbolic machine learning as dualizing monotone boolean functions

Sergei O. Kuznetsov - Higher School of Economics A natural problem setting in machine learning is shown to be equivalent to the problem of dualizing a monotone boolean function. The most classical form of dualization setting is converting a DNF to CNF. The complexity of a solution depends on particular machine learning setting, which defines the type of the structure where dualization takes place. Several intractability and tractability results are discussed.