28.Гипотеза p≠np и ее обоснование

Мы уже знаем, что P NP. Как показал Ладнер, если P≠ NP , то имеется еще целое множество языков в NP, для которых нет полиномиального алгоритма, но сами эти языки не являются полными в классе NP.

В качестве кандидатов на такие языки выступают следующие две известные задачи.

ЗАДАЧА ИЗОМОРФИЗМ ГРАФОВ. Пусть даны два графа. Спрашивается, можно ли так пронумеровать их вершины, что их матрицы инциденций полностью совпадут (читай – один граф можно целиком наложить на другой и наоборот).

ПРОБЛЕМА ПРОВЕРКИ ПРОСТОТЫ ЧИСЛА. Эта проблема имеет важное значение для криптографии (шифрования). Известные алгоритмы проверки чисел на простоту являются переборными

Пусть L какой-нибудь произвольный язык из NP. Под дополнением языка L понимаем язык co-L, такой что

co-L  NP

если произвольное слово (задача) y принадлежит L, то у не принадлежит co-L. Наоборот, если y принадлежит co-L, то у не принадлежит L.

29.Смотри конспект!

30.Распознавание регулярных языков

Рассмотренная нами распознающая машина Тьюринга (вопрос 7) является частным вариантом общей машины Тьюринга, так как использует упрощенный набор правил. На самом деле этот специфический вариант машины называют автоматом. Имеются различные типы автоматов. Мы остановимся только на простейших (или регулярных) автоматах. Удобно правила регулярного автомата представлять в виде следующих формул

Qi a_k  Qj (*)

Такое правило читается следующим образом: если автомат находится в состоянии Qi и поступает символ a_k , то автомат переходит в состояние Qj.

Для того чтобы построить таблицу разбора для регулярного автомата достаточно

Каждому правилу (*) сопоставить фрагмент таблицы следующего вида

. . . . . . .	ak
Qi	Qj

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

a+5*c

a-b+c*10-d

a

Пусть в состоянии Q0 ожидается поступление буквы или числовой константы. В состоянии Q1 ожидается поступление знака операции. В состоянии Q2 ожидаем поступления цифры или знака операции. Отсюда получаем правила:

Q0 буква → Q1

Q1 знак_операции → Q0

Q0 цифра→ Q2

Q2 знак_операции → Q0

Q2 цифра → Q2

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

Имеет место следующий интересный результат.

Теорема. Всякий недетерминированный регулярный автомат можно реализовать с помощью эквивалентного детерминированного регулярного автомата.