Вопрос 28. Временная и ленточная сложности мт, вычисляющей заданную функцию. Теоремы о верхней границе сложности вычислений. Теорема об ускорении

t_T(x) – временная сложность, число тактов машины Т для вычисления функции f(x). Если функция f(x) не определена, то t_T(x) неопределенна.

Активной зоной при работе машины Т на числе Х называется связное мн-во, содержащие все ячейки ленты, которые были активными (т.е. использовались при вычислении значения функции) в процессе работы машины Т.

S_T(x) – длина активной зоны при работе машины Т на числе х, если f(x) не определена, то и функция S_T(x) неопределенна.

S_T(x) – ленточная сложность машины Т

T = <{a₀,a₁...a_n}, {q₀,q₁,...q_m}, П>

S_T(x) ≤ x+1+t_T(x)

t_T(x) ≤ (m+1)S_T²(x)*n^S_T^(x)

О верхней оценке сложность вычислений

Существует ли рекурсивная ф-ия h(x), т.ч для любой вычислимой ф-ии f(x) существует машина T, вычисляющая её за время t_T(x)≤h(x) (если f(x) определена)?

Теорема: Для любой рекурсивной функции h(x) существует рекурсивная ф-ия f(x), т.ч.

_f ={0,1) и для любой машины Т, вычисляющей эту ф-ию найдется такое x=n, при котором t_T(n)>h(n).

Док-во:

f(x) = { sg_x(x) если _x(x) определено и t_Tx(x) ≤ h(x),

0 иначе

где _x(x) – ф-ия с номером x, соотв. машине T_x с номером x.

n- номер функции f, с условием, что f=_n

TX	0	...	n
T0	tT0(0) ≤h(0)
...		......
Tn			tT0(n) ≤h(n)

f(n) = sg_n(n) =>f(x) ≠ _x(x) т.к _x(x) ≠ sg_x(n)

Если T_n вычисляет f(x), то условие t_Tn(n) ≤ h(n) нарушено.

Сложно вычислимые функции

Теорема Для любой Р.Ф. h(x) существует Р.Ф. f(x) т.ч _f ={0,1) и для любой машины Т, вычисляющей f(x), начиная с некоторого X выполняется условие t_T(x) > h(x)

Теорема об ускорении

Для любой Р.Ф. r(x) сущ. Р.Ф. f(x) с условием, что _f ={0,1), т.ч какова бы ни была машина Т_i, вычисляющая ф-ию f(x) найдется машина T_j, вычисляющая эту функцию с условием, что t_Ti(x) > r(t_Tj(x)), начиная с некоторого x

Пример.

r(x) = 2^x

t_Tj < log₂(t_Ti(x))

t_Tk< log₂log₂(t_Ti(x))

Вопрос 29. Эффективности вычислений:

Z={z} – массовая задача

Исходные данные представленные в виде слов Р в конечном алфавите, зависящих от z.

Размерность - длина слов Р, кодирующего исходные данные задачи z.

Пример Вектор значений булевой функции.

Массовая задача решается эффективно (просто), если существует полином Q(x), такой что время решения каждой задачи z Ć Z не превосходит Q(e(z))

Эффективное вычисление – вычисление с полиномнальной сложностью.

Переборная задача 2^e(z)

Метод сводимости:

Массовая задача Z={z} полиномиально сводится к массовой задачи Z`={z`}, если существует словарная функция F, которая по произвольной задаче z Ć Z строит задачу F(z)=z`Ć Z`, что задача z имеет положительные ответ тогда когда z` имеет положительный ответ и время вычисления F(z) ограничено значением Q(e(z)), где Q(x) – некоторый полином, зависящий от массовых задач Z и Z`, но не от некоторых задач z и z`.

Пример. Задача о МДНФ сводится к задаче покрытия единиц множествами, образование К – мерной карты (карты корно).

Определение переборной задачи

Массовая задача Z называется переборной, если она может быть сформулирована в след. виде: по заданному значению z Ć Z выяснить, существует ли y, размерность которого e(y) не превосходит полинома e(z) и такой, что выполнено свойство R(z,y), поверяемое на машине Тьренга за время, ограниченное полиномом от e(z)+e(y). Перебор объектов y до тех пор, пока не выполнится R(z,y)

Число переборов растет по экспоненте.

1. z четно? z/y=2 Если y найден z=2y

2. Кодовый замок y – ключ.

3. f,g –булевы функции f=g

y=(q₁…….q_n) f(q₁…….q_n)=g(q₁…….q_n)

Переборная задача Z называется универсальной или полной, если любая ПЗ полиномиально к ней сводится.

1. Задача выполнимой булевой функции

2. Задача о полном подграфе

3. Задача о вершинном покрытии

Множество вершин таких, что каждое ребро графа инцедентно к некоторой вершине из этого множества.

4. Задача о существовании гамельтонова цикла в гафе.

5. Задача о раскраске графа.

6. Задача о изоморфном подграфе (для заданных графов G и G` установить существует ли в G` подграф, изоморфный графу G).