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



         

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


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

х ® 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.




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