| Abstrakt: | V práci sa zaoberáme neuniformnými výpočtovými modelmi, s dôrazom na branching programy, využívané hlavne na reprezentáciu postupností booleovských funkcií, skúmanie ich vlastností a výpočtovej zložitosti. Analyzujeme najvýznamnejšie výsledky z oblasti zložitosti branching programov, študujeme vplyv rôznych ohraničení na základný model. Pre explicitne definované postupnosti funkcií sa získavanie netriviálnych dolných odhadov považuje za ťažký problém. Prezentované náročné techniky na získavanie dolných odhadov sú aplikované na konkrétne postupnosti funkcií a jazykov. Na príkladoch ilustrujeme limity použiteľnosti a hranice kvality dolných odhadov dokázateľných jednotlivými technikami. Zjednocujúci pohľad na doteraz známe techniky a koncept bariér, ktoré treba prekonať, naznačuje smerovanie v študovanej oblasti.
|
|---|