Minimum epsilon-equivalent circuit size problem
For a Boolean function f given by its truth table (of length 2(n)) and a parameter s the problem considered is whether there is a Boolean function g epsilon-equivalent to f, i.e., Pr (xis an element of{0, 1}n) {g(x) not equal f(x)} less than or equal to epsilon, and computed by a circuit of size at most s. In this paper we investigate the complexity of this problem and show that for specific values of epsilon it is unlikely to be in P/poly. Under the same assumptions we also consider the optimization variant of the problem and prove its inapproximability.
inapproximability minimum circuit size problem approximation boolean circuits natural properties combinatorial optimization