Войти
Вычислительная сложность теория фокусируется на классификации вычислительных проблем в в соответствии с их использованием ресурсов и использования этих классов друг с другом. Вычислительная задача - это задача, решаемая компьютером. Вычислительная задача решается механическим применением математических шагов, таких как алгоритм.
. Проблема сложной по своей сути, если ее решение требует значительных ресурсов, независимо от используемого алгоритма. Теория формалирует эту интуицию, вводя математические модели вычислений для изучения этих проблем и количественно оценивая их вычислительную сложность, т. Е. Количество ресурсов, необходимых для их решений, таких как время и память.. Также используются другие меры сложности, такие как объем связи (используется в сложности связи ), количество вентилей в схеме (используется в сложности схемы ) и количество процессоров (используемых в параллельных вычисленийх ). Одна из ролей теории вычислений - определить практические ограничения того, что компьютеры и не могут делать. Проблема P против NP, одна из семи Задач Премии тысячелетия, посвящена области вычислительной сложности.
Тесно связанной области теоретической информатики: анализ алгоритмов и теории вычислимости. Ключевое различие между анализом алгоритмов и теорией вычислительной сложности состоит в том, что первая посвящена анализу количества ресурсов, необходимого конкретного алгоритму для решения проблемы, тогда как вторая задает более общий вопрос обо всех алгоритмах, которые могут быть использованы для решения ту же проблему. Точнее, теория вычислений пытается классифицировать проблемы, которые могут быть решены с использованием надлежащим ограниченных ресурсов. В свою очередь, наложение ограничений на доступные ресурсы - это то, что отличает вычислительную сложность от теории вычислимости: последняя теория задает вопрос, какие типы проблем в принципе могут быть решены алгоритмически.
Поездка коммивояжера по 14 городам Германии. A вычислительные задачи можно рассматривать как бесконечный набор экземпляров вместе с решением для каждого экземпляра. Входная плата для вычислительной проблемы называется экземпляром проблемы. В теории сложности вычислений проблема относится к абстрактному вопросу, который необходимо решить. Напротив, примером этой проблемы является довольно конкретное высказывание, которое может исходными данными для решения проблемы. Например, рассмотрим задачу проверки простоты. Экземпляр - это число (например, 15), и решение - «да», если число простое, и «нет» в этом случае (в этом случае 15 не является простым, и ответ - «нет»). Другими словами, экземпляр - это конкретный вход в проблему, решение - это выход, соответствующий данному входу.
Чтобы еще больше подчеркнуть разницу между проблемой и экземплярами, рассмотрим следующий пример версии задачи коммивояжера : существует ли решения маршрут длиной не более 2000 километров, проходящий через все из 15 сторон городов Германии? Количественный ответ на этот конкретный пример мало пригоден для решения других проблем, таких как запрос на обход всех участков в Милане, общая длина которых не превышает 10 км. По этой причине сложности вычислительных проблем, а не конкретных проблем.
При рассмотрении вычислительных проблем экземпляров проблемы является строка над алфавитом. Обычно в качестве алфавита являются двоичный алфавит (. Е. Набор {0,1}), и таким образом, строки предоставляют собой битовые строки. Как и в реальном компьютере, математические объекты, отличные от битовых строк, должны быть соответствующим образом закодированы. Например, могут быть закодированы в двоичной системе счисления, а графики могут быть закодированы напрямую через их матрицы последовательности или путем кодирования их списки совместимости в двоичном формате.
Даже несмотря на то, что некоторые доказательства теории сложности регулярно предполагают конкретный выбор входной кодировки, каждый пытается сохранить обсуждение достаточно абстрактным, чтобы не зависеть от выбора кодировки. Этого можно достичь, обеспечив эффективное преобразование разных представлений друг в друга.
A проблема решения имеет только два возможных выхода: да или нет (или поочередно 1 или 0) на любом входе. Проблемы принятия решений являются одними из центральных объектов исследования в теории сложности вычислений. Проблема принятия решения - это особый тип вычислительной задачи, ответ на которую либо да, либо нет, либо поочередно либо 1, либо 0. Проблема принятия решений может рассматриваться как формальный язык, где элементы языка являются экземплярами чей вывода - да, а нечлены - это те экземпляры, вывод которых - нет. Задача в том, чтобы решить с помощью алгоритма , является ли входная строка рассматриваемого формального языка. Если алгоритм, решающий эту проблему, возвращает ответ «да», говорят, что алгоритм принимает входную систему, иначе говорят, что он отклоняет ввод.
Пример решения проблемы следующий. Входными данными является произвольный график . Проблема состоит в том, чтобы определить, является ли данный граф связным или нет. Формальный язык, связанный с этой проблемой принятия решений, является набором всех связанных графов - чтобы получить точное определение языка, необходимо решить, как графы кодируются как двоичные строки.
A Функциональная проблема - это вычислительная проблема, при которой один (из общей функции ) ожидается для каждого входа, но выход более сложный, чем этот проблемы решения - то есть результат не просто да или нет. Известные примеры включают задачу коммивояжера и задачу целочисленной факторизации.
. Заманчиво думать, что понятие функциональных проблем намного богаче, чем понятие принятия решений. Однако на самом деле это не так, поскольку функциональные проблемы можно преобразовать в проблемы решения. Например, умножение двух целых чисел может быть выражено как набор троек (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)).
Аналогичные определения могут быть даны для требований к пространству. Хотя время и пространство являются наиболее известными ресурсами сложности, любая мера сложности может рассматривать как вычислительный ресурс. Меры сложности обычно с помощью аксиом сложности Блюма. Другие меры сложности, используемые в теории сложности, включают сложность связи, сложность схемы и сложность дерева решений.
Сложность алгоритма часто выражается с помощью большого обозначения.
Визуализация алгоритма быстрой сортировки , которая имеет среднюю производительность 
.лучший, худший и средний случай сложности уровня к трем различной способам временной сложности (или любой другой мера сложности) разных входов одинакового размера. Некоторые входные данные размера 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).
A Класс сложности - это набор задач связанной сложности. Более простые классы сложности определяются следующими факторами:
Некоторые классы сложности имеют сложные определения, которые не вписываются в эту структуру. Таким образом, типичный класс сложности имеет следующее определение:
Но ограничение времени вычислений некоторой конкретной функцией f (n) часто приводит к классам сложности, которые зависят от выбранной модели машины. Например, язык {xx | x - любая двоичная строка} может быть решена за линейное время на многоленточной машине Тьюринга, но обязательно требует квадратичного времени в модели однопленочных машин Тьюринга. Если мы допустим полиномиальные вариации времени выполнения, тезис Кобэма-Эдмондса утверждает, что «временные сложности в любых двух разумных и общих моделях вычислений полиномиально связаны» (Goldreich 2008, глава 1.2). Это формирует основу для класса сложности P, который представляет собой набор задач принятия решений, решаемых детерминированной машиной Тьюринга за полиномиальное время. Соответствующий набор функциональных задач: FP.
Представление отношения междуклассами сложности Многие важные классы сложности могут быть использованы ограничения времени или пространства, используя алгоритмом. Некоторые классы сложности задач решения, таким образом, следующие:
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Классы Логарифмического пространства (обязательно) не принять во внимание пробел необходимо представить проблему.
Оказывается, что PSPACE = NPSPACE и EXPSPACE = NEXPSPACE по теореме Сэвича.
Другие важные классы сложности включают BPP, ZPP и RP, которые с помощью вероятностных машин Тьюринга ; AC и NC, которые определены с помощью логических схем; и BQP и QMA, которые используются с использованием квантовых машин Тьюринга. #P - важный класс сложности задач подсчета (не решения задач). Такие классы, как ИП и AM, определяют с помощью интерактивных систем проверки. ALL - это класс всех задач решения.
Для классов сложности, определенным образом, желательно доказать, что ослабление требований (скажем) времени вычислить действительно определяет больший набор проблем. В частности, содержит DTIME (n), содержится в DTIME (n), было бы интересно узнать, является ли включение строгим. Что касается требований по времени и пространству, то ответ на такие вопросы дает теоремы о иерархии времени и пространства соответственно. Они называются теоремы иерархии, потому что они индуцируют правильную иерархию классов. Таким образом, существуют пары классов сложности, один из которых должным образом включен в другой. Выведя такие правильные включения множеств, мы можем перейти к количеству запросов о том, сколько еще требуется дополнительного пространства времени или чтобы увеличить количество проблем, которые могут быть решены.
Точнее, теорема об иерархии времени утверждает, что
.Теорема об иерархии пространства утверждает, что
.Теоремы о пространственной и временной иерархии составляют элементы разделения элементов сложности. Например, теорема иерархии времени говорит нам, что P строго содержится в EXPTIME, а теорема иерархии времени говорит нам, что L строго содержит в PSPACE.
Многие классы сложности с использованием концепции сокращения. Редукция - это превращение одной проблемы в другую. Он отражает неформальное представление о том, что проблема не менее сложна, чем другая проблема. Например, если проблема X может быть решена с использованием алгоритма для Y, X не сложнее, чем Y, и мы говорим, что X сводится к Y. Существует много различных типов редукций, основанных на методах сокращения, например Редукции Кука, редукции Карпа и редукции Левина, а также ограничения сложности редукций, такие как редукции за полиномиальное время или сокращения в логическом пространстве.
наиболее часто используется сокращение - это полиномиальное сокращение. сокращение времени. Это означает, что процесс редукции занимает полиномиальное время. Например, проблема возведения целого числа в квадрат может быть сведена к задаче умножения двух целых чисел. Это означает, что для возведения целого в квадрат можно использовать алгоритм умножения двух целых чисел. В самом деле, это можно сделать, подав один и тот же вход на оба входа алгоритма умножения. Таким образом, мы видим, что возведение в квадрат не сложнее умножения, поскольку возведение в квадрат можно свести к умножению.
Это мотивирует представление о том, что проблема сложна для класса сложности. Проблема X трудна для класса проблем C, если каждая проблема в C может быть сведена к X. Таким образом, никакая проблема в C не более сложная, чем X, поскольку алгоритм для X позволяет нам решить любую проблему в C. проблема зависит от типа используемого сокращения. Для классов сложности, превышающих P, обычно используются сокращения за полиномиальное время. В частности, набор трудных для НП задач - это набор НП-сложные задач.
Если проблема X находится в C и сложна для C, то X называется завершенным для C. Это означает, что X является самой сложной проблемой в C. (поскольку многие проблемы могут быть одинаково сложным, можно сказать, что X - одна из самых сложных проблем в C. Таким образом, класс NP-полных задач содержит самые сложные проблемы в том смысле, что они самые вероятные, не будут в P. Проблема P = NP не решена, возможность свести известную NP-полную проблему, Π 2, другую проблему, Π 1, будет означать, что не существует известных решений с полиномиальным временем для Π 1. Это связано с тем, что решение с полиномиальным временем для Π 1 даст решение с полиномиальным временем для Π 2. Точно так же, поскольку все проблемы NP могут быть сведены к набору, нахождение NP-полная задача, которая может быть решена за полиномиальное время, будет означать, что P = NP.
Схема классов сложности при условии, что P ≠ NP. Существование проблем в NP вне P и NP-полных в этом случае было установлено Ладнером. Класс сложности P часто используется как математическая абстракция, моделирующая те вычислительные задачи, которые выполняют действенный алгоритм. Эта гипотеза получила название тезиса Кобэма - Эдмондса. С другой стороны, класс сложности NP предлагает множество проблем, которые могут быть использованы, но для использования которых не известен эффективный алгоритм, задача выполненной выполнимости, проблема гамильтонова пути и проблема вершинного покрытия. Детерминированные машины Тьюринга являются специальными недетерминированными машинами Тьюринга, легко заметить, что каждая проблема в P также является членом класса NP.
Вопрос о том, равно ли P NP, является одним из наиболее важных открытых вопросов в теоретической информатике из-за большого значения решения. Если ответ положительный, можно показать, что многие важные проблемы имеют более эффективные решения. Целочисленного программирования в исследования операций, многие проблемы в логистике, предсказании структуры белка в биологии, и способность находить формальные доказательства теоремы чистой математики. Проблема P и NP - одна из Задач Премии тысячелетия, предложенных Математическим институтом Клея. За решение проблемы присуждается приз в размере 1000000 долларов США.
Ладнер показал, что если P≠ NP, то существуют проблемы в НП, которые не входят ни в P, ни в NP-complete . Такие задачи называются NP-промежуточными проблемы. проблема изоморфизма графов, проблема дискретного логарифма и проблема целочисленной факторизации являются примерами проблем, которые считаются NP-промежуточными. Это одни из очень немногих проблем, которых не известно, что они находятся в P или являются NP-полными .
. Проблема изоморфизма графов является вычислительной проблемой определения того, является ли два конечных графа являются изоморфными. Важной нерешенной проблемой теории сложности является вопрос о том, находится ли проблема изоморфизма графов в P, NP-полном или в NP-промежуточном. Ответ неизвестен, но считается, что проблема как минимум не НП-полная. Если изоморфизм является NP-полным, иерархия полиномиального времени схлопывается до своего второго уровня. Широко распространено мнение, что иерархия полиномов не коллапсирует до какого-либо конечного уровня, что изоморфизм графов не является NP-полным. Лучший алгоритм для этой проблемы, благодаря Ласло Бабаи и Юджину Люксу, имеет время выполнения 
Проблема целочисленной факторизации - это вычислительная проблема определения разложения на простые множители данного числа. Сформулированная как проблема решения, это проблема определения того, имеет ли входной коэффициент меньше k. Эффективный алгоритм целочисленной факторизации неизвестен, и этот факт основан на нескольких современных криптографических системах, таких как алгоритм RSA. Проблема целочисленной факторизации находится в NP и в co-NP (и даже в UP и co-UP). Если проблема - NP-complete, иерархия полиномиального времени схлопнется до своего первого уровня (т. Е. NP будет равняться co-NP ). Самый алгоритм для целочисленной факторизации - это решето общего числового поля, которое занимает время ![{ \ Displaystyle О (е ^ {\ left ({\ sqrt [{3}] {\ frac {64} {9}}} \ right) {\ sqrt [{3}] {(\ log n)}} {\ sqrt [{3}] {(\ log \ log n) ^ {2}}}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d50912fbf223d0bbadd2a028262414397fbee1a9)
Предполагается, что многие известные классы сложности неравны, но это не было доказано. Например, P⊆ NP⊆ PP ⊆ PSPACE, но возможно, что P= PSPACE . Если P не равно NP, то P также не равно PSPACE . Создано множество классов сложности между P и PSPACE, например RP, BPP, PP, BQP, MA, PHи т. Д., Возможно, что все эти классы сложности рухнут. в один класс. Доказательство того, что эти классы не равны, было бы большим прорывом в теории сложности.
Аналогичным образом, co-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-hard также неразрешимы в этом смысле.
Однако эта идентификация неточна: полиномиальное решение с большой степенью или большим ведущим коэффициентом быстро растет и может оказаться непрактичным для задач практического размера; и наоборот, решение с экспоненциальным временем, которое растет медленно, может быть практичным при реалистичных входных данных, или решение, которое занимает много времени в худшем случае, может занять некоторое время в большинстве случаев или средний случай.. Сказать, что проблема не в P, не означает, что все большие случаи проблемы сложны или даже что из них трудны. Например, было показано, что проблема решения в Арифметика Пресбургера не находится в P, однако были написаны алгоритмы, которые в большинстве случаев решают проблему в разумные сроки. Точно так же алгоритмы могут решить NP-полную задачу о ранце в широком диапазоне размеров менее чем за квадратичное время, а решатели SAT обычно обрабатывают большие экземпляры NP-Complete Boolean проблема выполнимости.
понять, почему алгоритмы экспоненциального времени обычно неприменимы на практике, рассмотрим программу, которая выполняет 2 операции перед остановкой. Для малых n, скажем 100, программа будет работать примерно 10 операций каждую секунду, что по порядку соответствует возрасту Вселенной.. Даже с гораздо более быстрым компьютерная программа будет полезна только для очень маленьких случаев, в этом смысле неразрешимость проблемы в некоторой степени не зависит от технического прогресса. Однако показатель степени Алгоритм времени, требующий 1.0001 операции, практичен, пока не станет достаточно большим.
Аналогично, алгоритм с полиномиальным временем не всегда практичен. Если время его работы, скажем, неразумно считать его эффективным, и он по-прежнему бесполезен, за исключением случаев. В самом деле, на практике даже алгоритмов часто непрактичны при реалистичных размерах задач.
Теория непрерывной сложности может относиться к теории сложности задач, используя непрерывные функции, аппроксимируемые дискретизацией, как описано в численным анализом. Один из подходов к теории сложности численного анализа сложной, основанной на информации.
Теория непрерывной сложности также может относиться к использованию сложности аналоговых вычислений, в использовании непрерывных динамических систем <399 используются>и дифференциальные уравнения. Теория управления может рассматривать как формулы вычислений, дифференциальные уравнения при моделировании непрерывных и гибридных дискретно-непрерывных систем.
Ранним примером анализа алгоритма анализа времени выполнения алгоритма Евклида, выполненный Габриэлем Ламе в 1844 году.
До того, как началось собственное исследование, прямо посвященное сложности алгоритмических проблем, различные исследователи заложили многочисленные основы. Наиболее влиятельным них было определение машины Тьюринга, данное Аланом Тьюрингом в 1936 году, которое оказалось очень надежным и гибким упрощением компьютера.
Начало систематических исследований вычислительной сложности приписывается в статье 1965 года «О вычислительной сложности алгоритмов» Юриса Хартманиса и Ричарда Э. Стернса, в котором могут быть обнаружены возможности временной сложности и пространственной сложности, а также доказаны теоремы об иерархии. Кроме того, в 1965 г. Эдмондс рассматривает "хороший" алгоритм как алгоритм, время работы которого ограничено полиномом входного размера.
Более ранние статьи, в которых изучаются задачи, решаемые машинами Тьюринга с ограниченными ограниченными ресурсами в определении линейных ограниченных автоматов Джоном Майхиллом (Myhill 1960), а также рудиментарных множеств Раймонда Смалляна (1961) как статья Хисао Ямада о вычислениях в реальном времени (1962). Несколько ранее Борис Трахтенброт (1956), пионер в этой области из СССР, изучил еще одну специфическую меру сложности. Как он вспоминает:
Однако [мой] первоначальный интерес [к теории автоматов] все больше откладывался в пользу вычислительной сложности, захватывающего слияния комбинаторных методов, унаследованных от теории переключений, с концептуальным арсенал теории алгоритмов. Эти идеи мне в голову пришли ранее, в 1955 году, когда я ввел термин «сигнализирующая функция», который в настоящее время широко известен как «мера сложности».
В 1967 году Мануэль Блюм сформулировал набор аксиомы (теперь известные как аксиомы Блюма ), определяющие желаемые свойства сложности на множестве вычислимых функций и важные важные важные результат, так называемую теорему об ускорении. Эта область начала процветать в 1971 году, когда Стивен Кук и Леонид Левин доказали существование практически актуальных проблем, которые NP-полны. В 1972 году Ричард Карп совершил рывок вперед в своей знаменательной статье «Сводимость среди комбинаторных проблем», в которой он показал, что 21 разнообразный комбинаторный и теоретико-графовый задач, каждая из которых печально известна своей вычислительной сложностью, являются NP-полными.
В 1980-х годах было проделано много работы по средней сложности решения NP-полных задач - как точно, так и приблизительно. В то время вычислительной сложности на пике, и было широко распространено мнение, что если проблема оказывается NP-полной, то шансов на то, чтобы работать с ней в практической ситуации, было мало. Общие асимптотические факторы утверждают, что некоторые из наиболее очевидных результатов практики.
 | Викискладе есть материалы, связанные с теорией вычислительной сложности. |
