Сложность вычислений: теоретические основы и границы решаемости.

Введение

В теоретической информатике и математике теория вычислительной сложности фокусируется на классификации вычислительных задач в соответствии с использованием ими ресурсов и установлении связей между этими классами. Вычислительная задача – это задача, решаемая компьютером. Вычислительная задача может быть решена механическим применением математических шагов, таких как алгоритм. Задача считается принципиально сложной, если её решение требует значительных ресурсов, независимо от используемого алгоритма. Теория формализует эту интуицию, вводя математические модели вычислений для изучения этих задач и количественной оценки их вычислительной сложности, то есть количества ресурсов, необходимых для их решения, таких как время и память. Также используются и другие меры сложности, такие как объём коммуникации (в теории сложности коммуникации), количество логических элементов в схеме (в теории сложности схем) и количество процессоров (в параллельных вычислениях). Одной из задач теории вычислительной сложности является определение практических ограничений возможностей компьютеров. Проблема P против NP, одна из семи задач тысячелетия, является частью области вычислительной сложности. Тесно связанными областями в теоретической информатике являются анализ алгоритмов и теория вычислимости. Ключевое различие между анализом алгоритмов и теорией вычислительной сложности заключается в том, что первый посвящен анализу количества ресурсов, необходимых конкретному алгоритму для решения задачи, в то время как второй задаёт более общий вопрос обо всех возможных алгоритмах, которые могут быть использованы для решения одной и той же задачи. Более точно, теория вычислительной сложности пытается классифицировать задачи, которые могут или не могут быть решены при заданных ограничениях на ресурсы. В свою очередь, именно наложение ограничений на доступные ресурсы отличает вычислительную сложность от теории вычислимости: последняя изучает, какие типы задач могут быть решены алгоритмически в принципе.

Проблематические случаи

Вычислительную задачу можно рассматривать как бесконечное множество экземпляров вместе с набором (возможно, пустым) решений для каждого экземпляра. Входная строка для вычислительной задачи называется экземпляром задачи и не должна смешиваться с самой задачей. В теории вычислительной сложности под проблемой понимается абстрактный вопрос, который требуется решить. В отличие от этого, экземпляр этой проблемы – это достаточно конкретное задание, которое может служить входными данными для задачи принятия решения. Например, рассмотрим задачу проверки на простоту. Экземпляр – это число (например, 15), а решение – "да", если число простое, и "нет" в противном случае (в данном случае 15 не является простым, и ответ – "нет"). Иными словами, экземпляр – это конкретный вход для задачи, а решение – это выход, соответствующий данному входу. Чтобы еще больше подчеркнуть разницу между задачей и экземпляром, рассмотрим следующий экземпляр задачи коммивояжера (в варианте принятия решения): существует ли маршрут длиной не более 2000 километров, проходящий через все 15 крупнейших городов Германии? Количественный ответ на этот конкретный экземпляр задачи мало полезен для решения других экземпляров, например, для запроса маршрута в обе стороны по всем объектам в Милане, общая длина которого не превышает 10 км. По этой причине теория сложности изучает вычислительные задачи, а не конкретные экземпляры задач.

Представление проблемных экземпляров

При рассмотрении вычислительных задач, экземпляр задачи представляет собой строку над алфавитом. Обычно алфавит принимается за двоичный (то есть множество {0,1}), и, следовательно, строки являются битовыми строками. Как и в реальном компьютере, математические объекты, отличные от битовых строк, должны быть соответствующим образом закодированы. Например, целые числа можно представить в двоичном виде, а графы можно закодировать непосредственно через матрицы смежности или путем кодирования списков смежности в двоичном виде. Хотя некоторые доказательства теорем теории сложности часто опираются на конкретный выбор кодирования входных данных, стремятся поддерживать обсуждение достаточно абстрактным, чтобы оно не зависело от выбора кодирования. Этого можно достичь, обеспечив возможность эффективного преобразования различных представлений друг в друга.

Проблемы принятия решений в качестве формальных языков

Проблемы принятия решений являются одним из центральных объектов изучения в теории вычислительной сложности. Проблема принятия решений — это особый тип вычислительной задачи, ответ на которую может быть только «да» или «нет», либо 1 или 0. Проблему принятия решений можно рассматривать как формальный язык, где членами языка являются экземпляры, для которых ответ «да», а не-членами — экземпляры, для которых ответ «нет». Цель состоит в том, чтобы с помощью алгоритма определить, является ли заданная входная строка элементом рассматриваемого формального языка. Если алгоритм, решающий эту задачу, возвращает ответ «да», то говорят, что алгоритм принимает входную строку, иначе — отклоняет её. Примером проблемы принятия решений является следующая задача. На вход подаётся произвольный граф. Задача состоит в том, чтобы определить, является ли данный граф связным или нет. Формальный язык, соответствующий этой задаче принятия решений, — это множество всех связных графов. Чтобы получить точное определение этого языка, необходимо определить способ кодирования графов в виде двоичных строк.

Проблемы с функцией

Функциональная задача — это вычислительная задача, в которой для каждого входа ожидается единственный выход (значение функции), но этот выход сложнее, чем у задачи принятия решения, то есть выход не ограничивается ответом «да» или «нет». Яркими примерами являются задача коммивояжёра и задача факторизации целых чисел. Может показаться, что понятие функциональных задач значительно богаче понятия задач принятия решений. Однако это не совсем так, поскольку функциональные задачи можно свести к задачам принятия решений. Например, умножение двух целых чисел можно представить в виде множества троек (a, b, c), удовлетворяющих соотношению a × b = c. Проверка, принадлежит ли заданная тройка этому множеству, эквивалентна решению задачи умножения двух чисел.

Измерение размера экземпляра

Чтобы измерить сложность решения вычислительной задачи, можно оценить время, необходимое лучшему алгоритму для её решения. Однако время работы алгоритма может зависеть от конкретного экземпляра задачи. В частности, для решения более крупных экземпляров потребуется больше времени. Таким образом, время, необходимое для решения задачи (или объём требуемой памяти, или любая другая мера сложности), вычисляется как функция размера экземпляра. Обычно под размером экземпляра понимается размер входных данных в битах. Теория сложности изучает, как масштабируются алгоритмы при увеличении размера входных данных. Например, в задаче определения связности графа, во сколько раз увеличится время решения для графа с 2n вершинами по сравнению с графом с n вершинами? Если размер входных данных равен n, то время работы можно выразить как функцию от n. Поскольку время работы для разных входных данных одного и того же размера может отличаться, сложность алгоритма в худшем случае, T(n), определяется как максимальное время работы для всех входных данных размера n. Если T(n) является полиномом от n, то алгоритм называется полиномиальным. Тезис Кобэма утверждает, что задача может быть решена за разумное количество ресурсов, если для неё существует полиномиальный алгоритм.

Машины Тьюринга

Машина Тьюринга — это математическая модель универсальной вычислительной машины. Это теоретическое устройство, которое манипулирует символами, содержащимися на ленте. Машины Тьюринга не предназначены в качестве практической вычислительной технологии, а скорее как общая модель вычислительной машины — от передового суперкомпьютера до математика с карандашом и бумагой. Считается, что если проблему можно решить алгоритмом, то существует машина Тьюринга, которая решает эту проблему. Фактически, это и есть формулировка тезиса Черча — Тьюринга. Кроме того, известно, что всё, что можно вычислить на других моделях вычислений, известных нам сегодня, таких как машина RAM, Игра жизни Конвея, клеточные автоматы, лямбда-исчисление или любой язык программирования, можно вычислить на машине Тьюринга. Поскольку машины Тьюринга легко анализировать математически и считается, что они столь же мощны, как и любая другая модель вычислений, машина Тьюринга является наиболее часто используемой моделью в теории сложности. Для определения классов сложности используются различные типы машин Тьюринга, такие как детерминированные машины Тьюринга, вероятностные машины Тьюринга, недетерминированные машины Тьюринга, квантовые машины Тьюринга, симметричные машины Тьюринга и чередующиеся машины Тьюринга. В принципе, все они равномощны, но когда ресурсы (например, время или память) ограничены, некоторые из них могут быть более эффективными, чем другие. Детерминированная машина Тьюринга — это самая простая машина Тьюринга, которая использует фиксированный набор правил для определения своих будущих действий. Вероятностная машина Тьюринга — это детерминированная машина Тьюринга с дополнительным запасом случайных битов. Возможность принимать вероятностные решения часто помогает алгоритмам решать задачи более эффективно. Алгоритмы, использующие случайные биты, называются рандомизированными алгоритмами. Недетерминированная машина Тьюринга — это детерминированная машина Тьюринга с добавленной функцией недетерминированности, которая позволяет машине Тьюринга иметь несколько возможных будущих действий из данного состояния. Один из способов представить недетерминированность заключается в том, что машина Тьюринга разветвляется на множество возможных вычислительных путей на каждом шаге, и если она решает проблему хотя бы на одном из этих путей, считается, что она решила проблему. Очевидно, что эта модель не предназначена для физической реализации, это просто теоретически интересная абстрактная машина, порождающая особенно интересные классы сложности. Примеры можно найти в разделе «Недетерминированный алгоритм».

Другие модели машин

В литературе было предложено множество моделей машин, отличных от стандартных многоленточных машин Тьюринга, например, машины с произвольным доступом к памяти. Возможно, удивительно, но каждую из этих моделей можно преобразовать в другую, не предоставляя дополнительных вычислительных возможностей. Время и объем используемой памяти в этих альтернативных моделях могут различаться. Общим для всех этих моделей является то, что машины работают детерминированно. Однако некоторые вычислительные задачи легче анализировать с точки зрения более необычных ресурсов. Например, недетерминированная машина Тьюринга – это вычислительная модель, которой разрешено ветвиться, чтобы одновременно проверять множество различных возможностей. Недетерминированная машина Тьюринга мало связана с тем, как мы физически хотим вычислять алгоритмы, но её ветвление точно отражает многие математические модели, которые мы хотим анализировать, поэтому недетерминированное время является очень важным ресурсом при анализе вычислительных задач.

Меры сложности

Для точного определения того, что значит решить проблему, используя заданное количество времени и памяти, используется вычислительная модель, такая как детерминированная машина Тьюринга. Время, необходимое детерминированной машине Тьюринга M для обработки входных данных x, – это общее количество переходов состояний, или шагов, которые машина выполняет до остановки и выдачи ответа ("да" или "нет"). Говорят, что машина Тьюринга M работает за время f(n), если время, необходимое M для каждого входа длины n, не превышает f(n). Задача принятия решения A может быть решена за время f(n), если существует машина Тьюринга, работающая за время f(n), которая решает эту задачу. Поскольку теория сложности интересуется классификацией задач по их сложности, определяются множества задач на основе определенных критериев. Например, множество задач, решаемых за время f(n) на детерминированной машине Тьюринга, обозначается как DTIME(f(n)). Аналогичные определения могут быть даны для требований к памяти. Хотя время и память – наиболее известные ресурсы сложности, любая мера сложности может рассматриваться как вычислительный ресурс. Меры сложности в общем случае определяются аксиомами сложности Блума. Другие меры сложности, используемые в теории сложности, включают сложность коммуникации, сложность схем и сложность дерева решений. Сложность алгоритма часто выражается с помощью нотации "большое O".

Наилучшая, худшая и средняя сложность случаев

Наилучшая, наихудшая и средняя сложность случаев относятся к трем различным способам измерения временной сложности (или любой другой меры сложности) для различных входных данных одного размера. Поскольку некоторые входные данные размера n могут решаться быстрее, чем другие, мы определяем следующие типы сложности:

Сложность наилучшего случая: это сложность решения задачи для наилучших входных данных размера n.

Сложность среднего случая: это сложность решения задачи в среднем. Эта сложность определяется только относительно вероятностного распределения входных данных. Например, если предполагается, что все входные данные одного размера равновероятны, то сложность среднего случая может быть определена относительно равномерного распределения по всем входным данным размера n.

Амортизированный анализ: амортизированный анализ рассматривает как дорогостоящие, так и менее дорогостоящие операции вместе, на протяжении всей последовательности операций алгоритма.

Сложность наихудшего случая: это сложность решения задачи для наихудших входных данных размера n.

Порядок от наименее затратного к наиболее затратному: наилучший, средний (для дискретного равномерного распределения), амортизированный, наихудший.

Например, рассмотрим детерминированный алгоритм сортировки quicksort. Он решает задачу сортировки списка целых чисел, подаваемого на вход. Наихудший случай наступает, когда опорный элемент всегда является наибольшим или наименьшим значением в списке (в этом случае список никогда не разделяется). В этом случае алгоритм занимает время O(n²). Если предположить, что все возможные перестановки входного списка равновероятны, то среднее время сортировки составляет O(n log n). Наилучший случай возникает, когда каждый выбор опорного элемента делит список пополам, что также требует времени O(n log n).

Верхняя и нижняя границы сложности задач

Для классификации времени вычислений (или аналогичных ресурсов, таких как потребление памяти) полезно продемонстрировать верхнюю и нижнюю границы максимального времени, необходимого наиболее эффективному алгоритму для решения данной задачи. Сложность алгоритма обычно рассматривается как сложность в наихудшем случае, если не указано иное. Анализ конкретного алгоритма относится к области анализа алгоритмов. Чтобы показать верхнюю границу T(n) для временной сложности задачи, достаточно продемонстрировать существование алгоритма с временем работы не более T(n). Однако доказать нижнюю границу гораздо сложнее, поскольку нижняя граница делает утверждение обо всех возможных алгоритмах, решающих данную задачу. Фраза "все возможные алгоритмы" включает не только известные на сегодняшний день алгоритмы, но и любые алгоритмы, которые могут быть открыты в будущем. Чтобы показать нижнюю границу T(n) для задачи, необходимо доказать, что ни один алгоритм не может иметь временную сложность меньше T(n). Верхние и нижние границы обычно выражаются с использованием нотации «большое O», которая скрывает константные факторы и младшие члены. Это делает границы независимыми от конкретных деталей используемой вычислительной модели. Например, если T(n) = 7n² + 15n + 40, в нотации «большое O» это записывается как T(n) = O(n²).

Определение классов сложности

Класс сложности — это набор задач со связанной сложностью. Более простые классы сложности определяются следующими факторами:
Тип вычислительной задачи: Наиболее часто используемые задачи — это задачи принятия решений. Однако классы сложности могут быть определены на основе функциональных задач, задач подсчёта, задач оптимизации, задач с обещанием и т. д. Модель вычислений: наиболее распространённой моделью вычислений является детерминированная машина Тьюринга, но многие классы сложности основаны на недетерминированных машинах Тьюринга, булевых схемах, квантовых машинах Тьюринга, монотонных схемах и т. д. Ресурс (или ресурсы), который ограничивается, и предел этого ограничения: эти два свойства обычно указываются вместе, например, «полиномиальное время», «логарифмическое пространство», «постоянная глубина» и т. д. Некоторые классы сложности имеют сложные определения, которые не укладываются в эту структуру. Таким образом, типичный класс сложности имеет следующее определение:

Набор задач принятия решений, разрешимых детерминированной машиной Тьюринга за время f(n). (Этот класс сложности известен как DTIME(f(n)).) Но ограничение времени вычисления сверху некоторой конкретной функцией f(n) часто приводит к классам сложности, которые зависят от выбранной модели машины. Например, язык {xx | x — любая двоичная строка} может быть решён за линейное время на многоленточной машине Тьюринга, но обязательно требует квадратичного времени в модели одноленточной машины Тьюринга. Если допустить полиномиальные вариации во времени выполнения, тезис Кобэма — Эдмондса утверждает, что «временные сложности в любых двух разумных и общих моделях вычислений полиномиально связаны». Это составляет основу для класса сложности P, который представляет собой набор задач принятия решений, разрешимых детерминированной машиной Тьюринга за полиномиальное время. Соответствующий набор функциональных задач — FP.

Сокращение

Многие классы сложности определяются с использованием понятия редукции. Редукция – это преобразование одной задачи в другую. Она отражает неформальное представление о том, что одна задача не сложнее другой. Например, если задачу X можно решить с помощью алгоритма для Y, то X не сложнее Y, и мы говорим, что X приводима к Y. Существует множество различных типов редукций, основанных на методе сведения, таких как редукции Кука, редукции Карпа и редукции Левина, а также на ограничении сложности редукций, например, редукции за полиномиальное время или редукции в логарифмическом пространстве. Наиболее часто используемой редукцией является редукция за полиномиальное время. Это означает, что процесс сведения занимает полиномиальное время. Например, задача возведения целого числа в квадрат может быть сведена к задаче умножения двух целых чисел. Это означает, что алгоритм умножения двух целых чисел можно использовать для возведения целого числа в квадрат. Действительно, это можно сделать, подав один и тот же ввод на оба входа алгоритма умножения. Таким образом, мы видим, что возведение в квадрат не сложнее умножения, поскольку возведение в квадрат приводимо к умножению. Это обосновывает понятие задачи, сложной для класса сложности. Задача X является сложной для класса задач C, если каждая задача в C приводима к X. Следовательно, ни одна задача в C не сложнее X, поскольку алгоритм для X позволяет решить любую задачу в C. Понятие сложных задач зависит от типа используемой редукции. Для классов сложности, больших чем P, обычно используются полиномиальные редукции. В частности, множество задач, сложных для NP, является множеством NP-трудных задач. Если задача X принадлежит C и сложна для C, то X считается полной для C. Это означает, что X – самая сложная задача в C. (Поскольку многие задачи могут быть одинаково сложными, можно сказать, что X – одна из самых сложных задач в C.) Таким образом, класс NP-полных задач содержит наиболее сложные задачи в NP, в том смысле, что они с наибольшей вероятностью не принадлежат P. Поскольку проблема P = NP не решена, возможность свести известную NP-полную задачу Π2 к другой задаче Π1 будет указывать на то, что неизвестно решения в полиномиальное время для Π1. Это связано с тем, что решение в полиномиальное время для Π1 привело бы к решению в полиномиальное время для Π2. Аналогично, поскольку все задачи NP могут быть сведены к множеству, нахождение NP-полной задачи, которую можно решить за полиномиальное время, означало бы, что P = NP.

Проблема P против NP

Класс сложности P часто рассматривается как математическая абстракция, моделирующая вычислительные задачи, для которых существует эффективный алгоритм. Эта гипотеза называется тезисом Кобэма — Эдмондса. Класс сложности NP, с другой стороны, содержит множество задач, которые хотелось бы эффективно решать, но для которых неизвестны эффективные алгоритмы, такие как задача об истинности высказываний, задача о гамильтоновом пути и задача о вершинном покрытии. Поскольку детерминированные машины Тьюринга являются частным случаем недетерминированных машин Тьюринга, легко заметить, что любая задача из P также принадлежит классу NP. Вопрос о том, равен ли P NP, является одним из важнейших нерешенных вопросов в теоретической информатике из-за далеко идущих последствий его решения. Если ответ утвердительный, то можно будет показать, что многие важные задачи имеют более эффективные решения. К ним относятся различные типы задач целочисленного программирования в исследовании операций, многие задачи в области логистики, предсказание структуры белков в биологии и возможность находить формальные доказательства теорем чистой математики. Проблема P против NP входит в число задач тысячелетия, предложенных Институтом математики Клэя. За решение этой проблемы предусмотрена награда в размере 1 000 000 долларов США.

Проблемы в NP, о которых не известно, что они находятся в P или NP-комплектных

Ладнер показал, что если P ≠ NP, то в NP существуют задачи, которые не принадлежат ни P, ни классу NP-полных задач. Если задача об изоморфизме графов является NP-полной, то полиномиальная иерархия схлопывается до второго уровня. Поскольку широко распространено мнение, что полиномиальная иерархия не схлопывается до какого-либо конечного уровня, считается, что задача об изоморфизме графов не является NP-полной. Наилучший алгоритм для этой задачи, разработанный Ласло Бабаем и Евгением Луксом, имеет время работы для графов с n вершинами, хотя некоторые недавние работы Бабая предлагают новые перспективные подходы к решению этой задачи. Задача факторизации целых чисел — это вычислительная задача определения разложения данного целого числа на простые множители. Формулируясь как задача принятия решения, она заключается в определении, имеет ли входное число простой делитель, меньший k. Эффективного алгоритма факторизации целых чисел не известно, и этот факт является основой для нескольких современных криптографических систем, таких как алгоритм RSA. Задача факторизации целых чисел принадлежит классам NP и co-NP (и даже UP и co-UP). Если задача является NP-полной, то полиномиальная иерархия схлопывается до первого уровня (то есть NP будет равно co-NP). Наиболее известный алгоритм для факторизации целых чисел — общее решето по числовым полям, требующее времени для факторизации нечетного целого числа n. Однако, наиболее известный квантовый алгоритм для этой задачи, алгоритм Шора, работает за полиномиальное время. К сожалению, этот факт мало что говорит о положении задачи относительно неквантовых классов сложности.

Различия между другими классами сложности

Многие известные классы сложности, как предполагается, неравны, но это не доказано. Например, P ⊆ NP ⊆ PP ⊆ PSPACE, но возможно, что P = PSPACE. Если P не равен NP, то P не равен PSPACE. Поскольку между P и PSPACE существует множество известных классов сложности, таких как RP, BPP, PP, BQP, MA, PH и т. д., возможно, что все эти классы сложности схлопываются в один класс. Доказательство неравенства любого из этих классов стало бы крупным прорывом в теории сложности. В том же ключе, co NP – это класс, содержащий задачи, дополняющие задачи NP (то есть задачи с обращенными ответами «да/нет»). Считается, что NP не равен co NP, однако это пока не доказано. Очевидно, что если эти два класса сложности не равны, то P не равен NP, поскольку P = co P. Таким образом, если P = NP, то co P = co NP, откуда следует NP = P = co P = co NP. Аналогично, неизвестно, строго ли L (множество всех задач, разрешимых в логарифмическом пространстве) содержится в P или равно P. Опять же, между ними существует множество классов сложности, таких как NL и NC, и неизвестно, различны ли они или равны. Предполагается, что P и BPP равны. Однако вопрос о том, равно ли BPP классу NEXP, остается открытым.

Втягиваемость

Проблема, которую можно решить в теории (например, при наличии больших, но конечных ресурсов, особенно времени), но для которой на практике любое решение требует слишком больших ресурсов, чтобы быть полезным, называется неразрешимой задачей. И наоборот, проблема, которую можно решить на практике, называется разрешимой задачей, буквально – «задачей, с которой можно справиться». Термин «неосуществимая» (буквально «невозможно выполнить») иногда используется как синоним «неразрешимой», хотя это может привести к путанице с допустимым решением в математической оптимизации. Разрешимые задачи часто отождествляются с задачами, имеющими решения за полиномиальное время (P, PTIME); это известно как тезис Кобэма — Эдмондса. Известны задачи, которые в этом смысле неразрешимы, включая задачи, являющиеся EXPTIME-трудными. Если NP не равно P, то NP-трудные задачи также неразрешимы в этом смысле. Однако это отождествление неточно: решение за полиномиальное время с большой степенью или большим старшим коэффициентом быстро растёт и может оказаться непрактичным для задач реального размера; наоборот, решение за экспоненциальное время, которое растёт медленно, может быть практичным для реалистичных входных данных, или решение, требующее много времени в худшем случае, может занимать мало времени в большинстве случаев или в среднем случае и, таким образом, всё ещё быть практичным. Утверждение о том, что задача не принадлежит классу P, не подразумевает, что все большие случаи задачи сложны или даже что большинство из них таковы. Например, задача принятия решений в арифметике Пресбургера была показана не принадлежащей классу P, но тем не менее были разработаны алгоритмы, решающие эту задачу за разумное время в большинстве случаев. Аналогично, алгоритмы могут решать NP-полную задачу о рюкзаке в широком диапазоне размеров менее чем за квадратичное время, а решатели SAT регулярно обрабатывают большие экземпляры NP-полной задачи булевой выполнимости. Чтобы понять, почему алгоритмы с экспоненциальным временем обычно непригодны для практического использования, рассмотрим программу, выполняющую 2ⁿ операций перед завершением. Для небольшого n, скажем, 100, и предполагая, что компьютер выполняет 10¹² операций в секунду, программа будет выполняться около 4 × 10¹⁰ лет, что сопоставимо с возрастом Вселенной. Даже с гораздо более быстрым компьютером программа будет полезна только для очень небольших экземпляров, и в этом смысле неразрешимость задачи в некоторой степени не зависит от технологического прогресса. Однако алгоритм с экспоненциальным временем, требующий 1,0001ⁿ операций, будет практичен до тех пор, пока n не станет относительно большим. Аналогично, алгоритм за полиномиальное время не всегда практичен. Если время его работы, скажем, n¹⁵, то считать его эффективным неразумно, и он всё равно бесполезен, за исключением небольших экземпляров. Действительно, на практике даже алгоритмы с n³ или n² часто непрактичны для задач реального размера.

Теория непрерывной сложности

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

История

Ранним примером анализа сложности алгоритма является анализ времени выполнения алгоритма Евклида, выполненный Габриэлем Ламе в 1844 году. До того, как начались исследования, непосредственно посвященные сложности алгоритмических задач, различные исследователи заложили многочисленные основы. Наиболее влиятельным среди них было определение машин Тьюринга Аланом Тьюрингом в 1936 году, которое оказалось очень надежным и гибким упрощением представления компьютера. Начало систематических исследований в области вычислительной сложности приписывается основополагающей работе 1965 года "О вычислительной сложности алгоритмов" Юриса Хартманиса и Ричарда Э. Стернса, в которой были сформулированы определения временной и пространственной сложности и доказаны теоремы о иерархии. Кроме того, в 1965 году Эдмондс предложил считать "хорошим" алгоритм тот, чье время выполнения ограничено полиномом от размера входных данных. Более ранние работы, изучающие задачи, разрешимые машинами Тьюринга с конкретными ограниченными ресурсами, включали исследования вычислений в реальном времени (1962). Еще раньше, Борис Трахтенброт (1956), пионер в этой области из СССР, изучал другую конкретную меру сложности. Как он вспоминает:

Однако, [мой] изначальный интерес [к теории автоматов] все больше уступал место вычислительной сложности – захватывающему сочетанию комбинаторных методов, унаследованных от теории переключения, и концептуального арсенала теории алгоритмов. Эти идеи пришли мне в голову еще в 1955 году, когда я ввел термин "сигнализирующая функция", который сегодня обычно известен как "мера сложности". В 1967 году Мануэль Блум сформулировал набор аксиом (ныне известных как аксиомы Блума), определяющих желательные свойства мер сложности для множества вычислимых функций, и доказал важный результат, так называемую теорему об ускорении. Эта область начала активно развиваться в 1971 году, когда Стивен Кук и Леонид Левин доказали существование практически значимых задач, являющихся NP-полными. В 1972 году Ричард Карп значительно продвинулся в этом направлении со своей основополагающей работой "Сократимость среди комбинаторных задач", в которой он показал, что 21 разнообразная комбинаторная и графотеоретическая задача, каждая из которых печально известна своей вычислительной неразрешимостью, является NP-полной.