RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive
Prikl. Diskr. Mat., 2011 Number 3(13), Pages 12–16 (Mi pdm331)
This article is cited in 3 papers

Theoretical Foundations of Applied Discrete Mathematics

On the complexity of proving that a Boolean function is not a binary read-once

A. A. Voronenko

M. V. Lomonosov Moscow State University, Moscow, Russia

Abstract: We show that it is sufficiently to present a linear number of values of a given Boolean function to prove that it is not read-once over the binary basis.

Keywords: read-once Boolean function, proof complexity.

UDC: 519.716


© Steklov Math. Inst. of RAS, 2024