On Uncertainty versus Size in Branching Programs

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