Теория вычислительной сложности - Computational complexity theory

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

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

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

Вычислительные проблемы

Путешествие коммивояжера по 14 городам Германии.

Проблемные экземпляры

А вычислительная проблема можно рассматривать как бесконечное собрание экземпляры вместе с решение для каждого экземпляра. Входная строка для вычислительной проблемы называется экземпляром проблемы, и ее не следует путать с самой проблемой. В теории сложности вычислений проблема относится к абстрактному вопросу, который необходимо решить. Напротив, примером этой проблемы является довольно конкретное высказывание, которое может служить исходными данными для решения проблемы. Например, рассмотрим проблему проверка на простоту. Экземпляр - это число (например, 15), и решение - «да», если число простое, и «нет» в противном случае (в этом случае 15 не является простым, и ответ - «нет»). Другими словами, пример является конкретным вкладом в проблему, а решение - это выход, соответствующий данному входу.

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

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

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

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

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

А проблема решения имеет только два возможных выхода, да или же нет (или поочередно 1 или 0) на любом входе.

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

Пример проблемы решения следующий. Вход произвольный график. Проблема состоит в том, чтобы определить, является ли данный граф связаны или нет. Формальный язык, связанный с этой проблемой принятия решения, тогда является набором всех связанных графов - чтобы получить точное определение этого языка, нужно решить, как графы кодируются как двоичные строки.

Функциональные проблемы

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

Заманчиво думать, что понятие функциональных проблем намного богаче, чем понятие проблем принятия решений. Однако на самом деле это не так, поскольку функциональные проблемы могут быть преобразованы в проблемы решения. Например, умножение двух целых чисел может быть выражено как набор троек (а, б, c) такое, что соотношение а × б = c держит. Решение, является ли данная тройка членом этого множества, соответствует решению задачи умножения двух чисел.

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

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

Если размер ввода п, затраченное время можно выразить как функцию п. Поскольку время, затрачиваемое на разные входы одного и того же размера, может быть разным, временная сложность наихудшего случая T (п) определяется как максимальное время, затрачиваемое на все входы размера п. Если T(п) - многочлен от п, то алгоритм называется полиномиальное время алгоритм. Тезис Кобэма утверждает, что проблема может быть решена с допустимым количеством ресурсов, если она допускает алгоритм с полиномиальным временем.

Модели машин и меры сложности

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

Иллюстрация машины Тьюринга

Машина Тьюринга - это математическая модель общей вычислительной машины. Это теоретическое устройство, которое манипулирует символами, содержащимися на полоске ленты. Машины Тьюринга задумывались не как практическая вычислительная технология, а скорее как общая модель вычислительной машины - от продвинутого суперкомпьютера до математика с карандашом и бумагой. Считается, что если проблема может быть решена с помощью алгоритма, существует машина Тьюринга, которая решает эту проблему. Действительно, это утверждение Тезис Черча – Тьюринга. Кроме того, известно, что все, что можно вычислить на других известных нам сегодня моделях вычислений, таких как RAM машина, Игра жизни Конвея, клеточные автоматы или любой язык программирования может быть вычислен на машине Тьюринга. Поскольку машины Тьюринга легко анализировать математически и считаются такими же мощными, как и любая другая модель вычислений, машина Тьюринга является наиболее часто используемой моделью в теории сложности.

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

Детерминированная машина Тьюринга - это самая простая машина Тьюринга, которая использует фиксированный набор правил для определения своих будущих действий. Вероятностная машина Тьюринга - это детерминированная машина Тьюринга с дополнительным набором случайных битов. Способность принимать вероятностные решения часто помогает алгоритмам более эффективно решать проблемы. Алгоритмы, использующие случайные биты, называются рандомизированные алгоритмы. Недетерминированная машина Тьюринга - это детерминированная машина Тьюринга с добавленной функцией недетерминизма, которая позволяет машине Тьюринга иметь несколько возможных будущих действий из данного состояния. Один из способов взглянуть на недетерминизм состоит в том, что машина Тьюринга разветвляется на множество возможных вычислительных путей на каждом шаге, и если она решает проблему в любой из этих ветвей, считается, что она решила проблему. Ясно, что эта модель не предназначена для того, чтобы быть физически реализуемой моделью, это просто теоретически интересная абстрактная машина, которая порождает особенно интересные классы сложности. Примеры см. недетерминированный алгоритм.

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

Многие модели машин отличаются от стандартных многоленточные машины Тьюринга были предложены в литературе, например машины с произвольным доступом. Как это ни удивительно, каждую из этих моделей можно преобразовать в другую без дополнительных вычислительных мощностей. Эти альтернативные модели могут отличаться по времени и памяти.^[2] Все эти модели объединяет то, что машины работают детерминированно.

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

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

Для точного определения того, что значит решить проблему с использованием заданного количества времени и пространства, используется вычислительная модель, такая как детерминированная машина Тьюринга используется. В необходимое время детерминированной машиной Тьюринга M на входе Икс это общее количество переходов между состояниями или шагов, которые машина выполняет перед тем, как остановится и выдаст ответ («да» или «нет»). Машина Тьюринга M говорят, что действует во времени ж(п) если время, необходимое для M на каждом входе длины п самое большее ж(п). Проблема решения А можно решить вовремя ж(п), если существует машина Тьюринга, работающая во времени ж(п), что решает проблему. Поскольку теория сложности интересуется классификацией проблем на основе их сложности, каждый определяет наборы проблем на основе некоторых критериев. Например, набор задач, решаемых во времени. ж(п) на детерминированной машине Тьюринга обозначается через DTIME (ж(п)).

Аналогичные определения могут быть даны для требований к пространству. Хотя время и пространство - самые известные ресурсы сложности, любые мера сложности можно рассматривать как вычислительный ресурс. Меры сложности обычно определяются Аксиомы сложности Блюма. Другие меры сложности, используемые в теории сложности, включают: сложность коммуникации, сложность схемы, и сложность дерева решений.

Сложность алгоритма часто выражается с помощью нотация большой O.

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

Визуализация быстрая сортировка алгоритм который имеет средняя производительность по кейсу ${displaystyle {mathcal {O}} (nlog n)}$.

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

1. Сложность в лучшем случае: это сложность решения проблемы для наилучшего ввода размера. п.
2. Средняя сложность: это сложность решения задачи в среднем. Эта сложность определяется только относительно распределение вероятностей над входами. Например, если предполагается, что все входные данные одного размера имеют одинаковую вероятность появления, средняя сложность случая может быть определена относительно равномерного распределения по всем входам размера п.
3. Амортизированный анализ: Амортизированный анализ рассматривает как дорогостоящие, так и менее затратные операции вместе на протяжении всей серии операций алгоритма.
4. Сложность наихудшего случая: это сложность решения проблемы для наихудшего ввода размера. п.

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

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

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

Чтобы классифицировать время вычислений (или аналогичные ресурсы, такие как потребление пространства), полезно продемонстрировать верхнюю и нижнюю границы максимального количества времени, необходимого наиболее эффективному алгоритму для решения данной проблемы. За сложность алгоритма обычно принимается его сложность наихудшего случая, если не указано иное. Анализ конкретного алгоритма относится к области анализ алгоритмов. Чтобы показать верхнюю границу Т(п) от временной сложности задачи, нужно только показать, что существует конкретный алгоритм с временем выполнения не более Т(п). Однако доказательство нижних оценок намного сложнее, поскольку нижние оценки содержат утверждение обо всех возможных алгоритмах, решающих данную проблему. Фраза «все возможные алгоритмы» включает не только алгоритмы, известные сегодня, но и любые алгоритмы, которые могут быть обнаружены в будущем. Чтобы показать нижнюю границу Т(п) для задачи требуется показать, что ни один алгоритм не может иметь временную сложность ниже, чем Т(п).

Верхняя и нижняя границы обычно указываются с использованием нотация большой O, который скрывает постоянные множители и меньшие члены. Это делает границы независимыми от конкретных деталей используемой вычислительной модели. Например, если Т(п) = 7п² + 15п + 40, в большой нотации O можно было бы написать Т(п) = O (п²).

Классы сложности

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

А класс сложности представляет собой набор задач смежной сложности. Классы более простой сложности определяются следующими факторами:

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

Некоторые классы сложности имеют сложные определения, которые не вписываются в эту структуру. Таким образом, типичный класс сложности имеет следующее определение:

Набор задач решения, решаемых детерминированной машиной Тьюринга во времени ж(п). (Этот класс сложности известен как DTIME (ж(п)).)

Но ограничение времени вычисления выше некоторой конкретной функцией ж(п) часто дает классы сложности, зависящие от выбранной модели машины. Например, язык {хх | Икс любая двоичная строка} может быть решена в линейное время на многоленточной машине Тьюринга, но обязательно требует квадратичного времени в модели однопленочной машины Тьюринга. Если мы допускаем полиномиальные вариации времени работы, Кобхэм-Эдмондс тезис утверждает, что «временные сложности в любых двух разумных и общих моделях вычислений полиномиально связаны» (Гольдрайх 2008, Глава 1.2). Это составляет основу класса сложности п, который представляет собой набор задач принятия решений, решаемых детерминированной машиной Тьюринга за полиномиальное время. Соответствующий набор функциональных задач FP.

Важные классы сложности

Представление отношения между классами сложности

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

Классы логарифмического пространства (обязательно) не принимают во внимание пространство, необходимое для представления проблемы.

Получается, что PSPACE = NPSPACE и EXPSPACE = NEXPSPACE на Теорема савича.

Другие важные классы сложности включают BPP, ЗПП и RP, которые определены с помощью вероятностные машины Тьюринга; AC и NC, которые определены с помощью логических схем; и BQP и QMA, которые определяются с помощью квантовых машин Тьюринга. #П является важным классом сложности задач подсчета (не задач решения). Такие классы, как IP и ЯВЛЯЮСЬ определены с использованием Интерактивные системы доказательств. ВСЕ это класс всех задач решения.

Теоремы об иерархии

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

Точнее, теорема об иерархии времени утверждает, что

${displaystyle {mathsf {DTIME}} {ig (} f (n) {ig)} subsetneq {mathsf {DTIME}} {ig (} f (n) cdot log ^ {2} (f (n)) {ig) }}$.

В теорема пространственной иерархии утверждает, что

${displaystyle {mathsf {DSPACE}} {ig (} f (n) {ig)} subsetneq {mathsf {DSPACE}} {ig (} f (n) cdot log (f (n)) {ig)}}$.

Теоремы о временной и пространственной иерархии составляют основу большинства результатов разделения классов сложности. Например, теорема иерархии времени говорит нам, что P строго содержится в EXPTIME, а теорема пространственной иерархии говорит нам, что L строго содержится в PSPACE.

Снижение

Многие классы сложности определены с использованием концепции сокращения. Редукция - это превращение одной проблемы в другую. Он отражает неформальное представление о том, что проблема не менее сложна, чем другая проблема. Например, если проблема Икс можно решить с помощью алгоритма для Y, Икс не сложнее, чем Y, и мы говорим, что Икс уменьшает к Y. Существует много различных типов редукций, основанных на методе редукции, например редукции Кука, редукции Карпа и редукции Левина, а также ограничений сложности редукций, таких как редукции за полиномиальное время или же сокращение пространства журнала.

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

Это мотивирует представление о том, что проблема сложна для класса сложности. Проблема Икс является жесткий для класса задач C если каждая проблема в C можно свести к Икс. Таким образом, нет проблем в C сложнее, чем Икс, поскольку алгоритм Икс позволяет решить любую проблему в C. Представление о сложных проблемах зависит от типа используемой редукции. Для классов сложности, превышающих P, обычно используются сокращения за полиномиальное время. В частности, набор трудных для NP задач - это набор NP-жесткий проблемы.

Если проблема Икс в C и тяжело для C, тогда Икс как говорят полный за C. Это означает, что Икс самая сложная проблема в C. (Поскольку многие проблемы могут быть одинаково сложными, можно сказать, что Икс одна из самых сложных проблем в C.) Таким образом, класс НП-полный Задачи содержат наиболее сложные проблемы в NP, в том смысле, что они, скорее всего, не находятся в P. Поскольку проблема P = NP не решена, имея возможность сократить известную NP-полную задачу,₂, к другой проблеме, Π₁, означало бы, что не существует известного решения за полиномиальное время для Π₁. Это связано с тем, что решение Π за полиномиальное время₁ даст решение за полиномиальное время для Π₂. Точно так же, поскольку все проблемы NP могут быть сведены к набору, поиск НП-полный задача, которая может быть решена за полиномиальное время, будет означать, что P = NP.^[3]

Важные открытые проблемы

Схема классов сложности при условии, что P ≠ NP. Существование в NP задач вне P и NP-полных в этом случае было установлено Ладнером.^[4]

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

Класс сложности P часто рассматривается как математическая абстракция, моделирующая те вычислительные задачи, которые допускают эффективный алгоритм. Эта гипотеза называется Кобхэм – Эдмондс. Класс сложности НП, с другой стороны, содержит много проблем, которые люди хотели бы решить эффективно, но для которых не известен эффективный алгоритм, например Проблема логической выполнимости, то Гамильтонова проблема пути и проблема покрытия вершины. Поскольку детерминированные машины Тьюринга являются специальными недетерминированными машинами Тьюринга, легко заметить, что каждая проблема в P также является членом класса NP.

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

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

Ладнер показал, что если п ≠ НП тогда есть проблемы в НП которые ни в п ни НП-полный.^[4] Такие проблемы называются НП-средний проблемы. В проблема изоморфизма графов, то задача дискретного логарифмирования и проблема целочисленной факторизации являются примерами задач, которые считаются NP-промежуточными. Это одни из очень немногих проблем NP, о которых не известно. п или быть НП-полный.

В проблема изоморфизма графов вычислительная проблема определения того, являются ли две конечные графики находятся изоморфный. Важной нерешенной проблемой теории сложности является вопрос о том, находится ли проблема изоморфизма графов в п, НП-полный, или NP-промежуточный. Ответ неизвестен, но считается, что проблема как минимум не NP-полная.^[8] Если изоморфизм графов NP-полный, то полиномиальная временная иерархия рушится до второго уровня.^[9] Поскольку широко распространено мнение, что иерархия полиномов не коллапсирует до какого-либо конечного уровня, считается, что изоморфизм графов не является NP-полным.Лучший алгоритм для этой проблемы, благодаря Ласло Бабай и Евгений Лукс время выполнения ${displaystyle O (2 ^ {sqrt {nlog n}})}$ для графиков с п вершины, хотя некоторые недавние работы Бабая предлагают некоторые потенциально новые перспективы на этот счет.^[10]

В проблема целочисленной факторизации вычислительная задача определения простые множители заданного целого числа. Выражаясь как проблема решения, это проблема определения того, имеет ли входной простой коэффициент меньше, чем k. Эффективный алгоритм целочисленной факторизации неизвестен, и этот факт лежит в основе нескольких современных криптографических систем, таких как ЮАР алгоритм. Проблема целочисленной факторизации находится в НП И в со-НП (и даже в UP и Co-UP^[11]). Если проблема в НП-полный, иерархия полиномиального времени схлопнется до своего первого уровня (т. е. НП будет равно со-НП). Самый известный алгоритм целочисленной факторизации - это общее числовое поле сито, что требует времени ${displaystyle O (e ^ {left ({sqrt [{3}] {frac {64} {9}}} ight) {sqrt [{3}] {(log n)}} {sqrt [{3}] { (журнал журнал n) ^ {2}}}})}$^[12] разложить на множители нечетное целое число п. Однако наиболее известные квантовый алгоритм для этой проблемы, Алгоритм Шора, выполняется за полиномиальное время. К сожалению, этот факт мало что говорит о том, где находится проблема в отношении классов неквантовой сложности.

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

Предполагается, что многие известные классы сложности неравны, но это не было доказано. Например п ⊆ НП ⊆ PP ⊆ PSPACE, но возможно, что п = PSPACE. Если п не равно НП, тогда п не равно PSPACE либо. Поскольку существует множество известных классов сложности между п и PSPACE, Такие как RP, BPP, PP, BQP, MA, PHи т. д., возможно, что все эти классы сложности сведутся к одному классу. Доказательство того, что эти классы не равны, было бы большим прорывом в теории сложности.

В том же духе, со-НП это класс, содержащий дополнять проблемы (т.е. проблемы с да/нет обратные ответы) из НП проблемы. Считается^[13] который НП не равно со-НП; однако это еще не доказано. Понятно, что если эти два класса сложности не равны, то п не равно НП, поскольку п=co-P. Таким образом, если п=НП мы бы хотели иметь co-P=со-НП откуда НП=п=co-P=со-НП.

Точно так же не известно, если L (набор всех задач, которые могут быть решены в логарифмическом пространстве) строго содержится в п или равно п. Опять же, между ними есть много классов сложности, например NL и NC, и неизвестно, являются ли они разными или равными классами.

Есть подозрение, что п и BPP равны. Однако в настоящее время он открыт, если BPP = NEXP.

Несговорчивость

Проблема, которая может быть решена теоретически (например, при наличии больших, но ограниченных ресурсов, особенно времени), но для которой на практике любой решение требует слишком много ресурсов, чтобы быть полезным, это называется неразрешимая проблема.^[14] И наоборот, проблема, которая может быть решена на практике, называется разрешимая проблемабуквально «проблема, с которой можно справиться». Период, термин невыполнимый (буквально «невозможно сделать») иногда используется как синоним несговорчивый,^[15] хотя это рискует ошибиться с возможное решение в математическая оптимизация.^[16]

Решаемые проблемы часто отождествляются с проблемами, которые имеют решения за полиномиальное время (п, PTIME); это известно как Кобхэм – Эдмондс. Проблемы, которые, как известно, трудноразрешимы в этом смысле, включают те, которые EXPTIME -жесткий. Если NP не совпадает с P, то NP-жесткий проблемы в этом смысле также неразрешимы.

Однако такая идентификация неточна: полиномиальное решение с большой степенью или большим ведущим коэффициентом быстро растет и может оказаться непрактичным для задач практического размера; и наоборот, решение с экспоненциальным временем, которое растет медленно, может быть практичным при реалистичных входных данных, или решение, которое занимает много времени в худшем случае, может занять короткое время в большинстве случаев или в среднем случае и, таким образом, по-прежнему быть практичным. Сказать, что проблема не в P, не означает, что все большие случаи проблемы сложны или даже что большинство из них трудны. Например, проблема решения в Арифметика пресбургера было показано, что он не находится в P, однако были написаны алгоритмы, которые в большинстве случаев решают проблему в разумные сроки. Точно так же алгоритмы могут решать NP-полную проблема с рюкзаком в широком диапазоне размеров менее чем за квадратичное время и SAT решатели регулярно обрабатывать большие экземпляры NP-complete Проблема логической выполнимости.

Чтобы понять, почему алгоритмы экспоненциального времени обычно неприменимы на практике, рассмотрим программу, которая делает 2^п операции перед остановкой. Для малых п, скажем 100, и предположим, что компьютер делает 10¹² операций каждую секунду, программа будет работать примерно 4 × 10¹⁰ лет, что по порядку величины возраст вселенной. Даже с гораздо более быстрым компьютером программа будет полезна только для очень маленьких случаев, и в этом смысле неразрешимость проблемы в некоторой степени не зависит от технического прогресса. Однако алгоритм экспоненциального времени, занимающий 1.0001^п операции практичны, пока п становится относительно большим.

Точно так же алгоритм полиномиального времени не всегда практичен. Если его время работы, скажем, п¹⁵, неразумно считать его эффективным, и он по-прежнему бесполезен, за исключением небольших случаев. Ведь на практике даже п³ или же п² алгоритмы часто непрактичны при реалистичных размерах задач.

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

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

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

История

Ранним примером анализа сложности алгоритма является анализ времени работы Евклидов алгоритм сделано Габриэль Ламе в 1844 г.

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

Начало систематических исследований вычислительной сложности приписывают основополагающей статье 1965 года «О вычислительной сложности алгоритмов» Юрис Хартманис и Ричард Э. Стернс, в котором изложены определения временная сложность и космическая сложность, и доказал теоремы об иерархии.^[20] Кроме того, в 1965 г. Эдмондс предложил считать "хорошим" алгоритмом алгоритм, время работы которого ограничено полиномом от входного размера.^[21]

Более ранние статьи, посвященные изучению задач, решаемых с помощью машин Тьюринга с конкретными ограниченными ресурсами, включают:^[20] Джон Майхилл определение линейно ограниченные автоматы (Myhill 1960), Раймонд Смуллян изучение рудиментарных множеств (1961), а также Хисао Ямада бумага^[22] по вычислениям в реальном времени (1962). Несколько раньше Борис Трахтенброт (1956), пионер в этой области из СССР, изучил еще одну особую меру сложности.^[23] Как он вспоминает:

Однако [мой] первоначальный интерес [к теории автоматов] все чаще откладывался в пользу вычислительной сложности, захватывающего слияния комбинаторных методов, унаследованных от теория переключения, с концептуальным арсеналом теории алгоритмов. Эти идеи пришли мне в голову ранее, в 1955 году, когда я ввел термин «сигнальная функция», который в настоящее время широко известен как «мера сложности».^[24]

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

В 1980-х годах было проделано много работы над средней сложностью решения NP-полных задач - как точно, так и приблизительно. В то время теория вычислительной сложности была на пике, и было широко распространено мнение, что если проблема оказывается NP-полной, то шансов на то, чтобы работать с ней в практической ситуации, было мало. Однако становилось все более очевидным, что это не всегда так.^{[нужна цитата ]}, а некоторые авторы утверждали, что общие асимптотические результаты часто не важны для типичных задач, возникающих на практике.^[26]

Смотрите также

Работает по сложности

• Вуппулури, Шьям; Дориа, Франсиско А., ред. (2020), Распутывая сложность: жизнь и творчество Грегори Чайтина, World Scientific, Дои:10.1142/11270, ISBN  978-981-12-0006-9

Рекомендации

Цитаты

Учебники

• Арора, Санджив; Варак, Вооз (2009), Вычислительная сложность: современный подход, Издательство Кембриджского университета, ISBN  978-0-521-42426-4, Zbl  1193.68112
• Дауни, Род; Товарищи, Майкл (1999), Параметризованная сложность, Монографии в области компьютерных наук, Берлин, Нью-Йорк: Springer-Verlag, ISBN  9780387948836
• Ду, Дин-Чжу; Ко, Кер-И (2000), Теория вычислительной сложности, Джон Уайли и сыновья, ISBN  978-0-471-34506-0
• Гарей, Майкл Р.; Джонсон, Дэвид С. (1979), Компьютеры и непреодолимость: руководство по теории NP-полноты, В. Х. Фриман, ISBN  0-7167-1045-5
• Гольдрайх, Одед (2008), Вычислительная сложность: концептуальная перспектива, Издательство Кембриджского университета
• ван Леувен, Ян, изд. (1990), Справочник по теоретической информатике (том А): алгоритмы и сложность, MIT Press, ISBN  978-0-444-88071-0
• Пападимитриу, Христос (1994), Вычислительная сложность (1-е изд.), Эддисон Уэсли, ISBN  978-0-201-53082-7
• Сипсер, Майкл (2006), Введение в теорию вычислений (2-е изд.), США: Thomson Course Technology, ISBN  978-0-534-95097-2

Обзоры

• Халил, Хатем; Улери, Дана (1976), "Обзор современных исследований сложности алгоритмов для уравнений с частными производными", Материалы Ежегодной конференции по - ACM 76, ACM '76: 197–201, Дои:10.1145/800191.805573, S2CID  15497394
• Повар, Стивен (1983), «Обзор вычислительной сложности» (PDF), Commun. ACM, 26 (6): 400–408, Дои:10.1145/358141.358144, ISSN  0001-0782, S2CID  14323396, заархивировано из оригинал (PDF) 22 июля 2018 г., получено 24 октября, 2017
• Фортноу, Лэнс; Гомер, Стивен (2003), «Краткая история вычислительной сложности» (PDF), Бюллетень EATCS, 80: 95–133
• Мертенс, Стефан (2002), "Вычислительная сложность для физиков", Вычислительная техника в науке и англ., 4 (3): 31–47, arXiv:cond-mat / 0012185, Bibcode:2002CSE ..... 4c..31M, Дои:10.1109/5992.998639, ISSN  1521-9615, S2CID  633346

внешняя ссылка

• Зоопарк сложности
• «Классы вычислительной сложности», Энциклопедия математики, EMS Press, 2001 [1994]
• Какие самые важные результаты (и статьи) в теории сложности, которые должен знать каждый?
• Скотт Ааронсон: Почему философы должны заботиться о сложности вычислений