6533b85efe1ef96bd12bf71d

RESEARCH PRODUCT

Jaunas sakarības starp Būla funkciju jutīgumu un bloku jutīgumu

subject

description

Darbā tiek pētīta neatrisināta problēma skaitļošanas sarežģītības teorijā – Būla funkciju jutīguma s(f) saistība ar tādiem sarežģītības mēriem kā bloku jutīgums bs(f) un sertifikātu sarežģītība C(f). Populāra hipotēze apgalvo, ka jutīgums ir polinomiāli saistīts ar bloku jutīgumu un bs(f) = O(s(f)^c) kādai konstantei c. Līdz šim labākais zināmais novērtējums no augšas abiem mēriem ir eksponenciāls, bs(f) ≤ C(f) ≤ 2^(s(f)-1) s(f) - s(f) + 1, bet labākie atrastie piemēri sasniedz tikai kvadrātisku atstarpi, bs(f) = Ω(s(f)^2). Šajā darbā tiek pierādīts jauns novērtējums no augšas, bs(f) ≤ C(f) ≤ max(2^(s(f)-1) (s(f) - 1/3), s(f)).