DocumentCode
2176809
Title
The effect of basis on size of Boolean expressions
Author
Pratt, V.R.
fYear
1975
fDate
13-15 Oct. 1975
Firstpage
119
Lastpage
121
Abstract
To within a constant factor, only two complexity classes of complete binary bases exist. We show that they are separated by at most O(nlog310), or about O(n2.095), complementing a result of Khrapchenko that establishes an order n2 lower bound.
Keywords
Boolean functions; Upper bound;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1975., 16th Annual Symposium on
Conference_Location
USA
ISSN
0272-5428
Type
conf
DOI
10.1109/SFCS.1975.29
Filename
4567867
Link To Document