Выполнили студенты 321 группы:

Аграновский Михаил

Брызгалов Антон

Мирошник Владислав

Смирнов Александр

Задача

Доказать, что задача «Составные числа» .

Постановка

Задано натуральное число . Составное ли оно, т.е. имеет ли ононатуральный неединичный и не равный делитель?

Решение

1. Генерация подсказки

В качестве подсказки для машины Тьюринга будем использовать всевозможные натуральные числа. Тогда генерация подсказки для каждой следующей машины Тьюринга будет заключаться в прибавлении единицы к предыдущей подсказке, то есть иметь сложность , где — длина подсказки. В случае поставленной задачи только на числах (где m – длина входа) может останавливаться ДМТ с положительным ответом.
Таким образом сложность генерации подсказки:

1. Деление уголком

В дальнейшем нам понадобится следующая Лемма:

Лемма (сложность деления уголком)

Временная сложность нахождения остатка (деления уголком): .

Доказательство леммы

Зададим делимое и делитель в двоичной системе.

• Делимое:

• Делитель:

Если , то остаток равен , частное — .

Иначе, то есть при , число шагов при делении уголком двух чисел, записанных в двоичной системе счисления, будет в точности . На каждом шаге число битовых операций вычитания будет ограничено , т.к. мы работаем с числами, представленными в двоичной системе. Таким образом, общее число битовых операций ограничено сверху .

Тогда число битовых операций не превосходит , и для них выполнена оценка .

Доказательство завершено.

Если подсказка является делителем числа, то ДМТ, обрабатывающая данную подсказку, дает положительный ответ, в противном случае ДМТ не останавливается.

Для оценки итоговой временной сложности нам необходимо будет выбрать максимальное время работы на ДМТ, давших положительных ответ. (Здесь под работой ДМТ понимается время на генерацию подсказки + время работы самого алгоритма).

Воспользуемся результатом рассуждений, приведенных выше. Генерация подсказки имеет сложность , алгоритм нахождения остатка имеет временную сложность , где — длина входных данных (числа ). Итоговая сложность ( ) ограничена полиномом от входных данных. Поэтому задача проверки, является ли число составным, принадлежит классу NP.