6533b822fe1ef96bd127db95

RESEARCH PRODUCT

Būla virkņu kopu jūtīgums

subject

description

Jūtīgums s(f) un bloku jūtīgums bs(f) ir divi plaši lietoti Būla funkciju sarežģītības mēri. Tie ir cieši saistīti ar daudziem citiem sarežģītības mēriem. Jautājums par asimptotisko attiecību starp šiem lielumiem jau ilgu laiku paliek neatrisināts, un vislabākais novērtējums sasniedz kvadrātisku atstarpi: bs(f) = Ω(s(f)^2). Darbā tiek risināts ar šo problēmu saistīts uzdevums: kāds ir mazākais iespējamais Būla virkņu kopas S ar jūtīgumu s izmērs pie nosacījuma, ka katra maska ar tieši k nofiksētiem bitiem satur vismaz vienu no S virsotnēm. Iepriekš tika atrisināts gadījums k = 0, un iegūtais rezultāts pielietots, lai uzlabotu asimptotiskās attiecības dažādiem funkciju sarežģītības mēriem. Šajā darbā tiek atrisināts gadījums k = 1, un gadījumam k = 2 tiek sniegts novērtējums no augšas minimālajam kopas S izmēram.