The representability of a Boolean function by a repetition-free formula can be verified by a circuit of linear complexity

DOI10.1515/156939205776368913zbMath1103.94306OpenAlexW2062303419MaRDI QIDQ5491249

A. A. Voronenko

Publication date: 10 October 2006

Published in: Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/156939205776368913

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30) Turing machines and related notions (03D10)

This page was built for publication: The representability of a Boolean function by a repetition-free formula can be verified by a circuit of linear complexity