Алгоритмы и анализ сложности (стр. 8 )

1. Для ее решения существует алгоритм.

2. К ней полиномиально сводится любая задача из .

Но любая задача – это задача распознавания цепочки языка, поэтому, заменив «задача» на «язык», получим другое определение сводимости:

Пусть имеются языки и . Если цепочку длины можно так преобразовать за время в цепочку , что будет допускаться тогда и только тогда, когда допускается , то полиномиально сводится к .

Преобразование производится за длина().

Задача выполнимости булевых формул

Пусть задана формула, содержащая булевы переменные, соединенные знаками операций . Если существует какой-нибудь набор значений переменных («истина» (1) или «ложь» (0)), при к-ром все выражение будет истинно, то формула является выполнимой.

Пример: при и произвольных и .

Задача выполнимости БФ играет особую роль: доказывается, что к ней сводится любая задача из .

С другой стороны показывается последовательная сводимость задачи выполнимости к другим задачам.

ычислительные машины и труднорешаемые задачи – приведено 300 задач.

Доказательство полноты задачи ВБФ

1. Для задачи ВБФ существует алгоритм.

Пусть булева формула длины содержит переменные .

for (k=1; k<=r; k++) x[k] = выбор(true, false);

if (F(x[1],…,x[r])) выход(“да”);

else выход(“нет”);

2. Любая задача из полиномиально сводится к задаче ВБФ, более формально:

Пусть – некоторый язык и НМТ, распознающая за полиномиальное время. На вход НМТ подана цепочка длины . Требуется показать, что по МТ и можно за время построить такую БФ, к-рая будет выполнима , когда НМТ допускает .

Булева формула будет «моделировать» последовательность МО НМТ: каждое присвоение 1 или 0 логическим переменным соответствует некоторой (возможно, незаконной) последовательности МО. БФ = 1 , когда соответствующая последовательность МО допускает .

Пусть НМТ выполняет ровно шагов, тогда она не может использовать ячеек ленты – будем считать, что на ленте занято ровно ячеек.

Введем переменные-индексы для булевых переменных БФ:

– такты времени, ;

– номер символа на ленте, , – длина алфавита;

– номер позиции на ленте, ;

– номер текущего состояния НМТ, , – число состояний НМТ.

Логические переменные для БФ:

ячейка в момент времени содержит символ с номером ;

в момент МТ находится в состоянии ;

  в момент МТ обозревает ячейку .

Вспомогательный предикат:

  ровно одна из переменных истинна ().

Длина данного предиката составляет .

Доказательство основано на том факте, что допускающая последовательность из МО удовлетворяет совокупности из 7 утверждений о функционировании НМТ.

Каждое утверждение описывает одна из частей БФ, а вся БФ строится как их конъюнкция: .

1. в любой момент времени УУ НМТ обозревает ровно одну ячейку ленты.

,  .

Длина.

2. в любой момент каждая клетка содержит 1 символ.