Теория алгоритмов. Зюзысов В.М. - 65 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

Будем говорить, что функция f: {0,1}
*
→ {0,1}
*
({0,1}
*
обозначает множество
битовых строк) вычислима за полиномиальное время, если существует
полиномиальный алгоритм A, который для любого x∈{0, 1}
*
выдает результат f(x).
Рассмотрим теперь множество I условий произвольной абстрактной задачи
разрешения. Два представления e
1
и e
2
этого множества называются полиномиально
связанными, если существуют две вычислимые за полиномиальное время функции f
12
и
f
21
, для которых f
12
(e
1
(i)) = e
2
(i) и f
21
(e
2
(i)) = e
1
(i) для всякого i∈I. Это значит, что e
1
–
представление входа может быть за полиномиальное время получено из e
2
–представления
и наоборот. В этом случае не имеет значения, какое из двух полиномиально связанных
представлений выбрать, как показывает следующая теорема.
Теорема 38. Пусть Q – абстрактная задача разрешения с множеством условий I, а
e
1
и e
2
– полиномиально связанные представления для элементов множества I.
Предположим, что множество всех строк, которые являются e
1
–представлениями
элементов Q, разрешимо за полиномиальное время, и что аналогичное свойство
выполнено для представления e
2
. Тогда свойства e
1
(Q)∈P и e
2
(Q)∈P равносильны.
Доказательство. Утверждение симметрично, так что достаточно доказать его в
одну сторону. Предположим, что задача e
1
(Q) разрешима за время Ο(n
k
) для некоторого
фиксированного числа k. По предположению для всякого условия i∈I представление e
1
(i)
может быть получено из представления e
2
(i) за время Ο(n
c
) (где c – некоторая константа, n
= |e
2
(i)|, |s| – обозначает длину строки s). Для решения задачи e
2
(Q), получив на входе e
2
(i),
мы сперва вычислим e
1
(i), а затем применим алгоритм, разрешающий e
1
(Q) к строке e
1
(i).
Сколько времени займет наше вычисление? Преобразование e
2
(i) в e
1
(i) требует
полиномиального времени. Следовательно, |e
1
(i)| = Ο(n
c
), поскольку длина выхода
алгоритма не превосходит времени его работы. Решение задачи с условием e
1
(i) занимает
Ο( |e
1
(i)|
k
) = Ο(n
ck
) времени. Итак, время вычисления оказалось полиномиальным. (Мы
пропустили важный момент: получив на входе некоторую строку, мы должны сначала
проверить, что она является e
2
–представлением некоторого входа; по предположению это
можно сделать за полиномиальное время.)
Представление объекта будем обозначать угловыми скобками: <G> – это
стандартное представление объекта G. При этом множество всех строк, являющихся
представлениями, является полиномиально разрешимым (существует полиномиальный
алгоритм, проверяющий по строке, представляет ли она какой-либо объект), а различные
«разумные» способы представления
данных оказываются полиномиально связанными, так
что можно воспользоваться теоремой 38 и не описывать представление детально, если нас
интересует лишь вопрос о полиномиальности задачи. Таким образом, в дальнейшем мы не
будем делать различия между абстрактной задачей и её строковым представлением, как
это обычно и делают.
6.2 Формальные языки
Для задач разрешения удобно использовать терминологию теории формальных
языков. Алфавитом Σ называется любой конечный набор символов. Языком L над
алфавитом Σ называется произвольное множество строк символов из алфавита Σ (такие
строки называются словами в алфавите Σ). Например, можно рассмотреть Σ = {0,1} и
язык L = {10, 11, 101, 111, 1011, 1101, 10001,…}, состоящий из двоичных записей простых
чисел.
Задача
разрешения (точнее, соответствующая ей строковая задача разрешения) является
языком над алфавитом Σ = {0,1}.

Страницы