We consider the problem of determining whether a given function f : {0, 1}{sup}n → {O, 1} belongs to a certain class of Boolean functions F{sub}P or whether it is far from the class. More precisely, given query access to the function f and given a distance parameter ε, we would like to decide whether f ∈ F{sub}P or whether it differs from every g ∈ F{sub}P on more than an ε fraction of the inputs. We give algorithms for testing monomials whose query complexity is O{sup}～(1/ε{sup}2) and for testing monotone DNF formulae with at most l terms whose query complexity is O{sup}～(l{sup}3/ε{sup}2).
展开▼
