For a Boolean function
f given by its truth table (of length
2n2^n
) and a parameter
s the problem considered is whether there is a Boolean function
g
e\epsilon
-equivalent to
f, i.e.,
Prx Î {0,1}n{g(x) ¹ f(x)} £ ePr_{x\in {\{0,1\}}^n}\{g(x) \ne f(x)\} \le \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
e\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.
minimum circuit size problem - approximation - Boolean circuits - inapproximability - natural properties - combinatorial optimization