On an approximate computation of the height of the maximal upper zero of a monotone Boolean function (Q1177787)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On an approximate computation of the height of the maximal upper zero of a monotone Boolean function |
scientific article |
Statements
On an approximate computation of the height of the maximal upper zero of a monotone Boolean function (English)
0 references
26 June 1992
0 references
The computing problem considered here is to estimate the height of the upper zero of a given monotonic Boolean function. An approximate oracle- algorithm is given to solve this problem. The algorithm is polynomial in the number of variables of the given Boolean function, and the accuracy of the approximation is related to the number of oracle-questions allowed.
0 references
upper zeros in Boolean hypercube
0 references
approximate algorithms
0 references
monotonic Boolean function
0 references
oracle-algorithm
0 references
