An upper bound for the circuit complexity of existentially quantified Boolean formulas
The expressive power of existentially quantified Boolean formulas ECNF with free variables is investigated. We introduce a hierarchy of subclasses EMU*(k) of ECNF formulas based on the maximum deficiency k of minimal unsatisfiable subformulas of the bound part of the formulas. We will establish an upper bound of the size of minimally equivalent circuits. It will be shown, that there are constants a and b, such that for every formula in EMU*(k) of length m of the bound part and length l of the free part of the formula there is an equivalent circuit of size less than l + a . m(b(log2(m)+k)2). (C) 2010 Elsevier B.V. All rights reserved.
circuits complexity quantified boolean formulas