The representability of a Boolean function by a repetition-free formula can be verified by a circuit of linear complexity
From MaRDI portal
Publication:5491249
DOI10.1515/156939205776368913zbMath1103.94306OpenAlexW2062303419MaRDI QIDQ5491249
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
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