On circuit complexity of partial Boolean functions

Chashkin A.V.

Abstract:

We estimate the circuit complexity of partial Boolean functions of a given weight in an arbitrary complete finite basis B, where each basis function φ_i is assigned a positive weight ρ_i, and the complexity of a circuit is the sum of the weights of all its gates. For any partial n-place Boolean function f defined on a domain of D≥n elements as equal to unity on N tuples from this domain, it is shown that as n→∞ L_B(f)≲ρ•(log₂(^D_N)/log₂log₂(^D_N))+O(n) where ρ is the minimum of reduced weights ρ_i/(r_i-1) of B taken over all nonunary gates of B.

Keywords:

partial Boolean function, weight of function, circuit complexity

Publication language: russian, pages: 71 (p. 152-222)

Research direction:

Mathematical problems and theory of numerical methods

Russian source text:

List of publications citation:

Export link to publication in format:

About authors:

Chashkin Alexander Viktorovich, ,