Opening book details…
Can I read Computation of Boolean functions by randomized programs on EtoBox?
Computation of Boolean functions by randomized programs by A.V. Chashkin is a Computer Science article available to read on EtoBox.
What is Computation of Boolean functions by randomized programs about?
The average time of computing Boolean functions by straight-line programs with random number generators is studied. Reliable programs, which always compute the correct value of the function in question, and programs computing the desired value with some probability are considered. In both cases, it is shown that random number generators do not lead to a noticeable reduction in the average execution time for a large portion of the inputs. More exactly, for any Boolean function of n arguments whose circuit size is L, there exists a domain for which the ratio of L to the average time of computing the function by reliable programs does not exceed n. For randomized programs with a probability di erent from 1, this ratio may be only slightly greater than n. ?
Who reads Computation of Boolean functions by randomized programs?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- A.V. Chashkin
- Publisher
- Elsevier Science; Elsevier ; Elsevier BV (ISSN 0166-218X)
- Published
- 2004
- Language
- EN
- Field
- Computer Science (Physical Sciences)