1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375), страница 26
Текст из файла (страница 26)
. . , qk aj → qku aju Su }исчерпываются все команды машины T , начинающиеся на qk aj → . . . Для каждого 1 6 l 6 u положим il = i − 1, если Sl = L; il = i, если Sl = Λ; il = i + 1,если Sl = R. Тогда формула Eijkt имеет вид:Eijkt = ¬Xhi, j, ki∨¬Zhi, ti∨¬Y hk, ti∨u ³_l=1´Xhi, jl , t+1i&Y hkl , t+1i&Zhil , t+1i .104Глава V.
Теория сложности алгоритмовСледовательно, формула E представляется в виде:E=& Eijkt.i,j,k,tКаждая Eijkt имеет ограниченную длину, не зависящую от n. Поэтому E имеетдлину O(p2 (n)).6) F утверждает, что первая конфигурация имеет вид q1 a0 wa0 . . . a0 (напомним,что все конфигурации состоят ровно из p(n) ячеек, поэтому первая конфигурация дополнена символами a0 ), т. е.³´ ³´F = Y h1, 0i&Zh1, 0i&Xh1, 0, 0i& & Xhi + 1, ji , 0i && Xhi, 0, 0i ,16i6nгде Y h1, 0i утверждает, что Tq1 ; Zh1, 0i утверждает, что Tленты; Xh1, 0, 0i утверждает,символ a0 ; & Xhi + 1, ji , 0i16i6nn+26i6p(n)в момент t = 0 находится в начальном состояниив момент t = 0 обозревает самую левую ячейкучто самая левая ячейка ленты вначале содержитутверждает, что следующие n ячеек вначале со-держат входное слово w (здесь w = aj1 aj2 .
. . ajn ); и, наконец,&Xhi, 0, 0in+26i6p(n)утверждает, что в начальный момент оставшиеся ячейки входной ленты заполнены символами a0 . Очевидно, что длина F равна O(p(n)).7) G утверждает, что последняя конфигурация имеет вид uq0 a1 v для некоторыхслов u, v. Для каждого 1 6 i 6 p(n) введем формулу Gi , которая утверждает,что в момент времени t = p(n) (т. е. после остановки) машина обозревает i-уюячейку ленты, в которой находится символ a1 .
Данная формула записываетсяследующим образом:Gi = Xhi, 1, p(n)i&Zhi, p(n)i.Тогда необходимая для нас формула G имеет следующий вид:G = Y h0, p(n)i&U (G1 , G2 , . . . , Gp(n) ),где Y h0, p(n)i утверждает, что в момент времени t = p(n) машина достигает заключительного состояния q0 , а U (G1 , G2 , . . . , Gp(n) ) утверждает, что послеостановки машина обозревает только одну ячейку ленты, в которой находитсясимвол a1 . Формула G имеет длину O(p2 (n)).Итак, положим Φ = A&B&C&D&E&F &G. Поскольку каждый из семи конъюнктивных членов состоит не более, чем из O(p3 (n)) символов, сама формула Φ такжесостоит не более, чем из O(p3 (n)) символов. Так как мы считали каждую пропозициональную переменную за один символ, а в действительности переменные представляются словами длины O(log10 n), то на самом деле верхней границей для длиныформулы Φ будет O(p3 (n) log10 n), а это не превосходит cnp3 (n), где c — некотораяконстанта.
Таким образом, длина формулы Φ полиномиально зависит от длины слова w. Нетрудно понять, что если заданы слово w и полином p, то формулу Φ можнозаписать за время, пропорциональное ее длине.По данной последовательности конфигураций M0 , M1 , . . . , Mq , приводящей к распознаванию слова w, можно, очевидно, найти такое присваивание значений 0 и 1пропозициональным переменным Xhi, j, ti, Y hk, ti и Zhi, ti, что формула Φ примет§ 27.
Теорема Кука105значение 1. И наоборот, если задано означивание переменых формулы Φ, при котором она принимает значение 1, то легко найти последовательность конфигурациймашины T , которая приводит к распознаванию слова w. Таким образом формула Φвыполнима тогда и только тогда, когда T распознает слово w.Язык L был произвольным языком из класса NP, и мы доказали, что L полиномиально сводится к проблеме выполнимости булевых формул.
Отсюда заключаем,что проблема выполнимости NP-полна.Список литературы1. Ершов Ю. Л. Теория нумераций. М.: Наука, 1977.2. Ершов Ю. Л., Палютин Е. А. Математическая логика. СПб.: Лань, 2004.3. Йех Т. Теория множеств и метод форсинга. М.: Мир, 1973.4. Касьянов В. Н. Лекции по теории формальных языков, автоматов и сложностивычислений. Новосибирск: НГУ, 1995.5. Мальцев А. И. Алгоритмы и рекурсивные функции. М.: Наука, 1986.6. Мендельсон Э. Введение в математическую логику.
М.: Наука, 1971.7. Морозов А. С. Введение в вычислимость, рукопись. [Электронный ресурс]. Режим доступа: http://math.nsc.ru/˜asm256/lect/lect.html8. Морозов А. С. Машины Шёнфилда: Методические указания. Новосибирск: НГУ,1996.9. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. М.:Мир, 1972.10. Соар Р. И. Вычислимо перечислимые множества и степени. Казань: Казанскоемат. общ-во, 2000.11. Khoussainov B., Nerode A.
Automata Theory and Its Applications. Boston:Birkhauser, 2001.12. Lewis H. R., Papadimitriou C. H. Elements of the Theory of Computation. N. J.:Plentice Hall, 1998.13. Shoenfield J. R. Recursion Theory, Lecture Notes in Logic. Berlin: Springer-Verlag,1993.Учебное изданиеКогабаев Нурлан ТалгатовичЛЕКЦИИ ПО ТЕОРИИ АЛГОРИТМОВУчебное пособиеРедактор Е. П. ВойтенкоПодписано в печать ??.??.2009 г.Формат 60×84 1/8.
Офсетная печать.Усл. печ. л. ?,?. Уч.-изд. л. ?,?. Тираж 100 экз.Заказ №Редакционно-издательский цент НГУ630090, Новосибирск-90, ул. Пирогова, 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
