[МУЗЫКА]
[МУЗЫКА] Однако
и с вычислительными функциями все не так хорошо и гладко.
Оказалось, что разные функции имеют разную вычислительную сложность.
При этом парадоксально, вычислительная сложность может быть определена не для
функции, а для алгоритма.
Мы могли бы попробовать определить вычислительную сложность функции как
сложность наилучшего алгоритма, реализующего эту функцию.
Но вы помните, что множество алгоритмов у нас бесконечно,
и здесь у нас могут быть две проблемы.
Первая — наилучшего алгоритма может просто не существовать.
Например, может существовать бесконечная последовательность алгоритмов каждый
из которых лучше, чем предыдущий.
Или наилучший алгоритм может быть нам неизвестен,
а проблема его поиска — неразрешима.
В этом случае мы можем определить сложность функции например как
сложность наилучшего алгоритма, реализующего эту функцию.
Мы не будем определять формально сложность вычисления класса сложности,
поскольку это тема отдельного курса.
Неформально сложность алгоритма это характер роста какого-то ресурса
(например, времени), необходимого для его выполнения в зависимости от размера задач.
Например, для сложения чисел в столбик нам нужно столько элементарных
табличных операций сложения сколько цифр в складываемых числах.
Например, если цифр n, нам требуется, учитывая переносы, 2n сложений.
Что соответствует сложности O(n).
При сортировке массива из n элементов методом «пузырька» нам
требуется O большое от n квадрат операций сравнения.
Вообще говоря, сортировка массива — очень хорошая функция.
Для нее нам известен теоретический предел сложности.
И алгоритмы, реализующие этот предел.
Таким образом, сортировка массива — это задача, у которой есть сложность.
Задачи такого рода, для которых сложность алгоритма оценивается
каким-то полиномом от размера входных данных, считаются «хорошими» и
составляют класс P — бесконечный класс задач,
для которых существуют полиномиальные алгоритмы.
Есть еще класс «условно хороших» задач,
для которых полиномиальные алгоритмы существуют для проверки решения.
К таким задачам относятся, например, поиск Гамильтонова пути в графе,
разложение чисел на множители и, например, сложение в столбик.
Если у нас есть полиномиальный алгоритм для решения задачи,
то мы его можем использовать как процедуру проверки решения.
Таким образом получается что класс P входит в класс NP (задач,
для которых существуют полиномиальные алгоритмы проверки решения).
Обратное включение — один из самых сложных
нерешенных вопросов современной теории вычислений.
В настоящий момент существуют задачи из класса P,
для которых неизвестен полиномиальный алгоритм.
Важные задачи.
Например, разложение числа на множители.
Предположим N состоит у нас из двух больших простых множителей.
Если числа p и q нам даны,
то мы можем легко полиномиально их перемножить и получить число N.
Однако если числа p и q неизвестны,
то в настоящий момент не существует эффективной процедуры их получения.
Представим, что вы придумали,
нашли два каких-то очень больших простых числа, тысяч по десять знаков.
Это можно сделать.
Перемножили их, получили число N.
Опубликовали его, а дальше забыли или потеряли числа p и q.
Теперь даже видя N, даже за время жизни
Вселенной существующими алгоритмами невозможно найти p и q.
Даже если искать будет компьютер размером со всю Вселенную.
Если гипотеза «P не равно NP» верна,
то класс NP на картинке будет выглядеть как-то так.
[БЕЗ_ЗВУКА] Задача
разложения на множители будет, вероятно, где-то здесь.
В 1994 году американский
математик Питер Шор предложил полиномиальный
алгоритм разложения чисел на множители для квантового компьютера.
Таким образом невыполнимая для классических вычислений задача
стала легко выполнима для квантовых вычислений.
Нарисуем на нашей картинке класс NP «трудных» задач.
[БЕЗ_ЗВУКА] Это такие задачи,
к которым полиномиально сводятся любая задача из NP.
Иными словами, если у нас есть волшебный ящик,
умеющий решать какую-то задачу из этого класса, из NP hard, то с помощью этого
волшебного ящика мы сможем эффективно решать любую задачу из NP.
В 1972 году Стивен Кук показал,
что пересечение класса NP hard NP не пусто.
Это пересечение называется «задача NP полная»,
или NP complete, или кратко NPC.
Для всех задач из класса NP в настоящий момент квантовые вычисления
дают лучший результат чем известные классические алгоритмы.
К сожалению этого нельзя сказать про класс NP трудных задач.
На последней неделе курса мы рассмотрим одну задачу из этого класса для которой мы
докажем, что квантовые вычисления дают не лучший результат, чем классические.
[БЕЗ_ЗВУКА]
Сысоев Сергей Сергеевичкандидат физико-математических наук
