Average time of computing Boolean operators

DOI10.1016/S0166-218X(02)00293-7zbMath0913.94029OpenAlexW2021828019MaRDI QIDQ4242300

A. V. Chashkin

Publication date: 10 May 1999

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(02)00293-7

zbMATH Keywords

complexityBoolean functionstraight-line programShannon's functionnon-branching program

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analytic circuit theory (94C05)

Related Items (4)

Mean computing time of Boolean operators by programs with restricted memory ⋮ On the average-case complexity of underdetermined functions ⋮ Bounds for the average-case complexity of monotone Boolean functions ⋮ An upper bound of unreliability of non-branching programs in an arbitrary complete finite basis for one-type constant faults at the outputs of computational operators

Cites Work

• Unnamed Item
• Average case complexity for finite Boolean functions

This page was built for publication: Average time of computing Boolean operators