Počet záznamů: 1
On Uncertainty versus Size in Branching Programs
- 1.0404104 - UIVT-O 20020142 RIV NL eng J - Článek v odborném periodiku
Jukna, S. - Žák, Stanislav
On Uncertainty versus Size in Branching Programs.
Theoretical Computer Science. Roč. 290, - (2003), s. 1851-1867. ISSN 0304-3975. E-ISSN 1879-2294
Grant CEP: GA ČR GA201/98/0717; GA MŠMT LN00A056; GA ČR GA201/02/1456
Klíčová slova: computational complexity * branching programs * decision trees * lower bounds * kraft inequality * entropy
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.764, rok: 2003
We propose an information-theoretic approach to proving lower bounds on the size of branching programs. The argument is based on Kraft type inequalities for the average amount of uncertainty about (or entropy of) a given input during the various stages of computation. We introduce a large class of 'balanced' branching programs and, using the suggested approach, prove that some explicit Boolean functions cannot be computed by balanced programs of polynomial size....
Trvalý link: http://hdl.handle.net/11104/0124375
Počet záznamů: 1