TY - JOUR AU - Andreev, Alexander E. PY - 1994/02/03 Y2 - 2024/03/29 TI - Complexity of Nondeterministic Functions JF - BRICS Report Series JA - BRICS VL - 1 IS - 2 SE - Articles DO - 10.7146/brics.v1i2.21668 UR - https://tidsskrift.dk/brics/article/view/21668 SP - AB - The 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.<br /> <br />We obtain an upper bound on the complexity of a nondeterministic function with restricted entropy for the worst case.<br /> <br /> 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).<br /> <br />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.<br /> <br />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. ER -