The power of probabilistic linear decision trees is examined. It is shown that the standard arguments used to prove lower bounds on deterministic linear decision trees apply to probabilistic linear decision trees as well. Examples are next given of problems which randomization helps solving.
|Original language||English (US)|
|Number of pages||14|
|Journal||Theoretical Computer Science|
|State||Published - 1985|
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)