Postroenie Algoritmov Dlya Zadach Bulevoy Logiki

Interes k dokazatel'stvu eksponentsial'nykh verkhnikh otsenok dlya NP-trudnykh zadach v poslednie neskol'ko desyatiletiy ostaetsya na stabil'no vysokom urovne. Odnim iz naibolee khorosho izuchennykh podkhodov k dokazatel'stvu takikh otsenok yavlyaetsya metod rasshchepleniya. Vpervye dannyy metod byl predlozhen v 1960 godu Devisom i Patnemom i sformulirovan v bolee sovremennom vide Devisom, Lodzhemannom i Lavlendom 1962 godu. Ego osnovnaya ideya zaklyuchaetsya v rasshcheplenii vkhodnogo primera zadachi na neskol'ko bolee prostykh primerov, takikh chto, postroiv reshenie dlya kazhdogo iz nikh, vozmozhno za polinomial'noe vremya postroit' reshenie dlya iskhodnogo primera. V rabote privodyatsya neskol'ko novykh podkhodov k razrabotke i analizu algoritmov rasshchepleniya dlya zadach bulevoy logiki. Opisyvaetsya komp'yuternaya programma dlya avtomaticheskogo analiza vremeni raboty takikh algoritmov. Takzhe pokazyvaetsya, kak s pomoshch'yu ispol'zovaniya zapominaniya diz"yunktov i kombinirovannykh mer slozhnosti poluchat' bolee sil'nye verkhnie otsenki na vremya raboty.