Конспект установочных лекций по комплексному курсу Информатика, Теория информации




Проблема выполнимости для булевских выражений


Булевское выражение логики высказываний образуется из идентификаторов, скобок, одноместного оператора и двухместных операторов n и v. Так что такое выражение является элементом формального языка, который через нетерминал <bе> описывается следующим БНФ-правилом:

<bе> ::= <id> ï Ø <bе> ô (<bе> Ù <bе>) ï (<bе> Ú <bе>)

Представим идентификаторы числами в их двоичном изображении. Тогда выражение длины n (с n символами) может быть представлено с помощью O(n log2n) знаков из некоторого конечного множества. Меру n для величины задачи положим равной длине булевского выражения. Точнее говоря, мы используем число знаков, необходимое для записи' выражения.

Проблема выполнимости lsat cостоит в выдаче ответа на следующий вопрос для заданного булевского выражения t: имеется ли такая конкретизация идентификаторов в t, при которой t может быть сведено к значению true?

Теорема. Проблема выполнимости lsat для булевского выражения является NP-полной.

Доказательство.

1.

lsat принадлежит классу NP: мы «угадываем» значения параметров для выполнимости и вычисляем значение формулы. Вычисление значения формулы полиномиально от n по времени, а угадывание полиномиально от n по памяти.

2.      Дадим доказательство того, что каждый недетерминированный полиномиально-ограниченный алгоритм может быть сведен за полиномиальное время к проблеме выполнимости lsat  исключительно для общей проблемы распознавания слова. Чтобы показать, что для каждого формального языка, чья проблема распознавания слова входит в NP, каждый алгоритм распознавания может быть сведен к lsat, для заданной  Т-машины М построим Т-машину М. Эта машина М реализует полиномиально-ограниченный алгоритм, получающий на входе слово х и порождающий булевское выражение Еx, которое точно тогда выполнимо, когда М принимает слово х. При этом М является р(n)-ограниченной по времени, а р(n) есть полином.

Теперь покажем, что каждая проблема из NP может быть за полиномиальное время сведена к lsat- B качестве недетерминированной Т-машины возьмем одноленточную правостороннюю машину (на ленте есть левый маркер).


Содержание  Назад  Вперед