Complexity of Nondeterministic Functions
AbstractThe complexity of a nondeterministic function is the minimum possible complexity of its determinisation. The entropy of a nondeterministic function, F, is minus the logarithm of the ratio between the number of determinisations of F and the number of all deterministic functions.
We obtain an upper bound on the complexity of a nondeterministic function with restricted entropy for the worst case.
These bounds have strong applications in the problem of algorithm derandomization. A lot of randomized algorithms can be converted to deterministic ones if we have an effective hitting set with certain parameters (a set is hitting for a set system if it has a nonempty intersection with any set from the system).
Linial, Luby, Saks and Zuckerman (1993) constructed the best effective hitting set for the system of k-value, n-dimensional rectangles. The set size is polynomial in k log n / epsilon.
Our bounds of nondeterministic functions complexity offer a possibility to construct an effective hitting set for this system with almost linear size in k log n / epsilon.
How to Cite
Andreev, A. (1994). Complexity of Nondeterministic Functions. BRICS Report Series, 1(2). https://doi.org/10.7146/brics.v1i2.21668
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.