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

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


Булевское выражение логики высказываний образуется из идентификаторов, скобок, одноместного оператора и двухместных операторов 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 качестве недетерминированной Т-машины возьмем одноленточную правостороннюю машину (на ленте есть левый маркер).
Пусть {bi}0£ i £р(n) - последовательность конфигураций Т- машины М, которая соответствует последовательности вычислений машины М, причем пусть каждое из n состоит в точности из р(n)+1 символов (р(n) символов ленты, и один символ - состояние машины). Если вычисление заканчивается раньше, чем будут выполнены р(n) шагов, то повторим конфигурацию конечного состояния нужное число раз, так что имеется ровно р(n)+1 конфигураций. Основные идеи аргументации по сводимости таковы.

·         Каждое вычисление машины М состоит из последовательности самое большее р(n)+1 конфигураций. Эта последовательность может быть представлена (р(n)+1)^2 знаками, если мы также и состояния закодируем знаками. Обратим внимание: за р(n) шагов машина М может рассмотреть самое большее р(n) ячеек ленты.



·         Для каждого знака z в представлении последовательности конфигураций введем булевскую переменную Ci,z (1£ i £ (р(n)+1)^2), которая принимает значение true точно тогда, когда i-й знак есть z.

·         Образуется булевское выражение, дающее значение true точно тогда, когда соответствующая последовательность соответствует принимающему вычислению.

·         Формула может быть порождена из входного слова для М с затратой времени О(р(n)^2).

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

# bо # b1— # bр(n)

есть последовательность вычислений, где #

b0 # -

это последовательность знаков с их номерами 0, 1, ..., р(n), р(n)+1 и т.д., а самый последний знак имеет номер (р(n)+1)^ причем этот последний знак есть # либо вновь введенный знак.

Для каждого знака z из алфавита Т-машины М, который может встретиться в таком вычислении, и для каждого числа i, 0£ i < (p(n)+l)^2 породим булевскую переменную Ci,z, которая задает, является ли i-й знак в последовательности конфигураций знаком z.


Образованное нами булевское выражение Еx точно тогда выполнимо, когда переменные Ci,z с присвоенными им значениями true

передают корректное вычисление.

В частности, Еx, естественно, должно быть таким, чтобы были справедливы следующие высказывания:

(1)"

i, l £ i < (p(n)+l)^2: $ x:Ci,x;

(2)        bо есть начальная конфигурация Т-машины М с входом х;

(3)        bр(n) есть принимающая конечная конфигурация;

(4)        bi ® bi+1 справедливо по заданному правилу.

Ex соответствует конъюнкции этих четырех высказываний. Точнее говоря, справедливо:

" i: ($ х: Ci,x) Ù Ø$ х, у,  у ¹ х: Ci,x Ù Ci,у.

(1)        Это записывается посредством формулы логики высказываний вида

Ф1Ù...ÙФ(р(n)+1)^2,

где

Фr =  ( Cr,a1 Ú Cr,a2 Ú…Ú Cr,ak) Ù (i,j(i¹j)(ØCr,i Ú ØCr,j))

(2)        Пусть х == <a1 ... аn> есть вход для Т-машины М. Приведенное выше высказывание (2) соответствует конъюнкции следующих высказываний:

(2i) cq,# Ù Cp(n)+i,# ,

(2ii) ci,yi Ú...Úc1,yk^,

 причем yi„ ..., у^ соответствуют знакам, которые кодируют знак а^ состояние qo и номер правила из k возможных, которое исходит из начального состояния qo и знака ai под головкой;

 (2iii)  " i Π {2, ..., п}: Ci,ai.

Остальные знаки а^, ..., an являются корректными.

 (2iv)  " i Π {n+1,..., р(n)}: Ci,#.

Выражение (3) говорит о том, что bр(n) является конечным состоянием. Как описание формулы логики высказываний получаем:

$ i, р(n)*р(n)+1) < i £ (р(n)+1)^2: ($ x Π F: Ci,x),

причем F обозначает множество новых (введенных нами) знаков, которые представляют конечное состояние.

(4)        То, что bi+1 вытекает из bi с помощью законного шага вычислений, проверяется высказыванием

"j, Р(n) < j < (р(n)+1)^2: $ w, х, у, w, x, y, :

Cj-l - (p(n)+l),w Ù Cj - (p(n)+l),x  Ù  Cj+l-(p(n)+l),y Þ Cj-l,w Ù Cj,x Ù Cj+l,y),



причем импликация записывается в случае, если для символа х функция перехода определена. Предполагается, что в машине Тьюринга операции записи и сдвига не объединяются в одной операции, т. е. имеют вид

х ® x', или ху ® хy, или wx ® wx.

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

# bo #…# bp(n) представляет собой корректно принимающее вычисление.

Можно показать, что формула Еx имеет длину О(р^2(n)). Она может быть порождена логарифмически ленточно-ограниченной Т-машиной

М из входа х. Действительно, Т-машине требуется лишь достаточно памяти, чтобы смочь считать до (р(n)+1)^2.

Поскольку log(p(n)+l)^2 = k*log n, достаточно 0(logn) памяти. Тем самым каждую проблему распознавания в NP можно свести к lsat  затратами памяти logspACE- Таким образом, lsat является NP-полной.

Пока не доказано ни Р = NP, ни Р ¹ NP, доказательство NP-полноты для какой-либо проблемы равносильно высказыванию, что для этой проблемы неизвестен какой-либо полиномиальный алгоритм. Если же удается задать полиномиальный алгоритм для NP-полной проблемы, то тем самым будет также доказано, что Р = NP.


Содержание раздела