Lower bounds for the complexity of restrictions of Boolean functions.

*(English)*Zbl 1006.94035Given a Boolean function \(f\) and a set \(M\) of domains, the circuit size complexity of the most complicated restriction of \(f\) to some domain in \(M\) is studied. Upper and lower bounds, depending on the domain size, are established for wide classes of Boolean functions. Similar results for other complexity measures (e.g., formula size) are given.

Reviewer: Heribert Vollmer (Würzburg)

##### MSC:

94C10 | Switching theory, application of Boolean algebra; Boolean functions (MSC2010) |

68Q25 | Analysis of algorithms and problem complexity |

03D15 | Complexity of computation (including implicit computational complexity) |

PDF
BibTeX
XML
Cite

\textit{A. V. Chashkin}, Discrete Appl. Math. 114, No. 1--3, 61--93 (2001; Zbl 1006.94035)

Full Text:
DOI

##### References:

[1] | A.E. Andreev, On the circuit complexity of partial boolean functions, Discrete Math. 4 (1989) 36-45 (in Russian). · Zbl 0719.94028 |

[2] | Chashkin, A.V., On estimates on the complexity of restrictions of Boolean functions, Dokl. math., 53, 3, 402-404, (1996) · Zbl 0891.94012 |

[3] | Chashkin, A.V., On the complexity of restrictions of Boolean functions, Discret. math. appl., 6, 3, 257-276, (1996) · Zbl 0891.94012 |

[4] | A.V. Chashkin, Average-case complexity of finite boolean functions, Discrete Appl. Math. 114 (2001) 43-59. · Zbl 1006.94034 |

[5] | E.G. Krasulina, On the complexity of implementing monotone symmetric boolean functions by contact circuits, Mathematical Problems in Cybernetics, Vol. 1, Moscow, Nauka, 1988, pp. 140-167 (in Russian). · Zbl 0668.94021 |

[6] | O.B. Lupanov, An approach to synthesis of control systems – the principle of local coding, Problems in Cybernetics, vol. 14, Moscow, Nauka, 1965, pp. 31-110 (in Russian). |

[7] | O.B. Lupanov, Asymptotic bounds for the complexity of control systems, Moscow, Mosk. Gos. Univ., 1984 (in Russian). |

[8] | L.A. Sholomov, On the implementation of partial boolean functions by circuits, Problems in Cybernetics 21, Moscow, Nauka, 1969, pp. 215-226 (in Russian). |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.