Complexity of Nondeterministic Functions
Alexander E. Andreev February 1994 |

## Abstract:The complexity of a nondeterministic function is the minimum
possible complexity of its determinisation. The entropy of a nondeterministic
function, 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 Our bounds of nondeterministic functions complexity offer a possibility to construct an effective hitting set for this system with almost linear size in .
Available as |

Last modified: 2003-06-08 by webmaster.