Opening book details…
Can I read An upper bound for complexity of polynomial normal forms of Boolean functions on EtoBox?
An upper bound for complexity of polynomial normal forms of Boolean functions by K. D. Kirichenko is a Computer Science article available to read on EtoBox.
What is An upper bound for complexity of polynomial normal forms of Boolean functions about?
We consider the problem of minimisation of Boolean functions in the class of polynomial normal forms. We suggest an algorithm for constructing polynomial normal forms for arbitrary Boolean functions such that the length of the obtained formula depends on the number of variables of the function only. As the input of the algorithm, along with the function, we take the solution of a covering problem. The number of elementary conjunctions in the obtained formula is equal to the cardinality of the covering. For the introduced covering problem we find an approximate solution. We succeed to prove that the complexity of Boolean functions in the class of polynomial normal forms is less than 2 nC1 .log 2 n C 1/=n, which allows us to conclude that for almost any Boolean function the complexity of its representation in the polynomial normal form is less than its representation in the disjunctive normal form.
Who reads An upper bound for complexity of polynomial normal forms of Boolean functions?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- K. D. Kirichenko
- Publisher
- Walter de Gruyter GmbH
- Published
- 2005
- Language
- EN
- Field
- Computer Science (Physical Sciences)