|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Randomized boolean decision trees: Several remarksстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 31 октября 2014 г.
- Автор: Vereshchagin N.
- Журнал: Theoretical Computer Science
- Том: 207
- Год издания: 1998
- Издательство: Elsevier BV
- Местоположение издательства: Netherlands
- Первая страница: 329
- Последняя страница: 342
- DOI: 10.1016/S0304-3975(98)00071-1
- Аннотация: Assume we want to show that (a) the cost of any randomized decision tree computing a given Boolean function is at least c. To this end, it suffices to prove that (b) there is a probability distribution over the set of all assignments to variables of that function with respect to which the average cost of any deterministic decision tree computing that function is at least c. Yao (1977) showed that this method is universal for proving lower bounds for randomized errorless decision trees, that is, that (a) is equivalent to (b). In the present paper we prove that this is the case also for randomized decision trees which are allowed to make errors. This gives the positive answer to the question posed in Yao (1977). In the second part of the paper we exhibit an example when randomized directional decision trees (defined in Yao (1977)) to evaluate read once formulae are not optimal. We construct a formula Fn of n Boolean variables such that the cost of the optimal directional decision tree computing Fn is Ω(nα) and there is an undirectional randomized decision tree computing Fn of cost O(nβ) for some β<α.
- Добавил в систему: Верещагин Николай Константинович