Postroenie algoritmow dlq zadach bulewoj logiki

Interes k dokazatel'stwu äxponencial'nyh werhnih ocenok dlq NP-trudnyh zadach w poslednie neskol'ko desqtiletij ostaetsq na stabil'no wysokom urowne. Odnim iz naibolee horosho izuchennyh podhodow k dokazatel'stwu takih ocenok qwlqetsq metod rasschepleniq. Vperwye dannyj metod byl predlozhen w 1960 godu Däwisom i Patnemom i sformulirowan w bolee sowremennom wide Däwisom, Lodzhemannom i Lawländom 1962 godu. Ego osnownaq ideq zaklüchaetsq w rasscheplenii whodnogo primera zadachi na neskol'ko bolee prostyh primerow, takih chto, postroiw reshenie dlq kazhdogo iz nih, wozmozhno za polinomial'noe wremq postroit' reshenie dlq ishodnogo primera. V rabote priwodqtsq neskol'ko nowyh podhodow k razrabotke i analizu algoritmow rasschepleniq dlq zadach bulewoj logiki. Opisywaetsq komp'üternaq programma dlq awtomaticheskogo analiza wremeni raboty takih algoritmow. Takzhe pokazywaetsq, kak s pomosch'ü ispol'zowaniq zapominaniq diz#ünktow i kombinirowannyh mer slozhnosti poluchat' bolee sil'nye werhnie ocenki na wremq raboty.