Počet záznamů: 1
On Uncertainty versus Size in Branching Programs
- 1.0404260 - UIVT-O 20010201 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
Jukna, S. - Žák, Stanislav
On Uncertainty versus Size in Branching Programs.
Electronic Colloquium on Computational Complexity. Report No.39. Trier, 2001, s. -. ISSN 1433-8092
Grant CEP: GA ČR GA201/98/0717; GA MŠMT LN00A056
Klíčová slova: computational complexity * branching programs * decision trees * lower bounds * Kraft inequality
Kód oboru RIV: BA - Obecná matematika
http://www.eccc.uni-trier.de/report/2001/039
Using an information-theoretic approach we prove a lower bound for so-called 'balanced' branching programs which for some classes of Boolean functions are more powerful than the most of previously considered restricted branching programs. The argument of the proof is based on an inequality for the average amount of uncertainty during the computation.
Trvalý link: http://hdl.handle.net/11104/0124523
Počet záznamů: 1