HomeIssuesOn the complexity of proving that a Boolean function is not abinary read-once

On the complexity of proving that a Boolean function is not abinary read-once | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2011. № 3(13).

We show that it is sufficientlyto present a linear number of values of a given Boolean function to prove that it is notread-once over the binary basis.
Download file
Counter downloads: 82
  • Title On the complexity of proving that a Boolean function is not abinary read-once
  • Headline On the complexity of proving that a Boolean function is not abinary read-once
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 3(13)
  • Date:
  • DOI
Keywords
proof complexity, read-once Boolean function, сложность доказательства, бесповторная булева функция
Authors
References
Вороненко А. А. О проверяющих тестах для бесповторных функций // Матем. вопросы кибернетики. Вып. 11. М.: Физматлит, 2002. С. 163-176.
Перязев Н. А. Слабоповторные булевы функции в бинарном базисе // Дискретная математика и информатика. Вып. 4. Иркутск: Изд-во Иркут. ун-та, 1998. 12 с.
Стеценко В. А. О предплохих базисах в P2 // Матем. вопросы кибернетики. Вып. 4. М.: Физматлит, 1992. С. 139-177.
On the complexity of proving that a Boolean function is not abinary read-once | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2011. № 3(13).
On the complexity of proving that a Boolean function is not abinary read-once | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2011. № 3(13).
Download full-text version
Counter downloads: 249
Download file