An upper bound for the circuit complexity of existentially quantified Boolean formulas
Autor: | A. Remshagen, H. Kleine Büning |
---|---|
Rok vydání: | 2010 |
Předmět: |
General Computer Science
Hierarchy (mathematics) Quantified Boolean formulas Complexity Expressive power Upper and lower bounds Theoretical Computer Science Combinatorics Circuits Computer Science::Logic in Computer Science Free variables and bound variables Equivalent circuit Deficiency k Circuit complexity Mathematics Electronic circuit Computer Science(all) |
Zdroj: | Theoretical Computer Science. 411(31-33):2864-2870 |
ISSN: | 0304-3975 |
DOI: | 10.1016/j.tcs.2010.04.017 |
Popis: | The expressive power of existentially quantified Boolean formulas @?CNF with free variables is investigated. We introduce a hierarchy of subclasses @?MU^*(k) of @?CNF 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 @?MU^*(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^(^l^o^g^"^2^(^m^)^+^k^)^^^2. |
Databáze: | OpenAIRE |
Externí odkaz: |
načítá se...