On estimates on the complexity of restrictions of Boolean functions (Q1380287)

The author finds lower bounds for the complexity of minimal contact and functional circuits that realize Boolean functions, in view of restrictions imposed on their domains. It is shown, in particular, that there exist partial functions having no circuits whose complexity and depth are close to the minimally possible ones at the same time. Proofs are not included.