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

Внутренняя сложность вычислительных задач

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

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

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

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

Тур коммивояжера по 14 городам Германии

Проблемные случаи

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

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

Представление проблемных случаев

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

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

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

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

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

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

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

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

Возникает соблазн думать, что понятие функциональных задач гораздо богаче понятия задач принятия решений. Однако это не совсем так, поскольку функциональные задачи можно переформулировать как задачи принятия решений. Например, умножение двух целых чисел можно выразить как набор троек, таких, что соотношение выполняется. Решение вопроса о том, является ли данная тройка членом этого набора, соответствует решению задачи умножения двух чисел. ${\displaystyle (a,b,c)}$ ${\displaystyle a\times b=c}$

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

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

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

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

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

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

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

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

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

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

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

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

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

Для точного определения того, что значит решить задачу, используя заданное количество времени и пространства, используется вычислительная модель, такая как детерминированная машина Тьюринга . Время, необходимое детерминированной машине Тьюринга на входе, представляет собой общее количество переходов состояний или шагов, которые машина делает, прежде чем остановится и выдаст ответ («да» или «нет»). Говорят, что машина Тьюринга работает за время , если время, требуемое для каждого входа длины, не превышает . Задача принятия решения может быть решена за время , если существует работающая за время машина Тьюринга, которая решает эту задачу. Поскольку теория сложности заинтересована в классификации задач на основе их сложности, мы определяем наборы задач на основе некоторых критериев. Например, набор задач, решаемых за время на детерминированной машине Тьюринга, обозначается как DTIME ( ). ${\displaystyle M}$ ${\displaystyle x}$ ${\displaystyle M}$ ${\displaystyle f(n)}$ ${\displaystyle M}$ ${\displaystyle n}$ ${\displaystyle f(n)}$ ${\displaystyle A}$ ${\displaystyle f(n)}$ ${\displaystyle f(n)}$ ${\displaystyle f(n)}$ ${\displaystyle f(n)}$

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

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

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

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

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

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

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

Например, детерминированный алгоритм сортировки quicksort решает проблему сортировки списка целых чисел. Худший случай — когда опорный элемент всегда является наибольшим или наименьшим значением в списке (поэтому список никогда не делится). В этом случае алгоритму требуется время O ( ). Если предположить, что все возможные перестановки входного списка равновероятны, среднее время, необходимое для сортировки, составляет . Лучший случай — когда каждый опорный элемент делит список пополам, что также требует времени. ${\displaystyle n^{2}}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(n\log n)}$

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

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

Верхние и нижние границы обычно указываются с использованием нотации big O , которая скрывает постоянные множители и меньшие члены. Это делает границы независимыми от конкретных деталей используемой вычислительной модели. Например, если , в нотации big O можно было бы написать . ${\displaystyle T(n)=7n^{2}+15n+40}$ ${\displaystyle T(n)=O(n^{2})}$

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

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

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

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

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

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

Но ограничение времени вычисления выше некоторой конкретной функцией часто дает классы сложности, которые зависят от выбранной модели машины. Например, язык может быть решен за линейное время на многоленточной машине Тьюринга, но обязательно требует квадратичного времени в модели одноленточной машины Тьюринга. Если мы допускаем полиномиальные вариации времени выполнения, тезис Кобэма-Эдмондса гласит, что «временные сложности в любых двух разумных и общих моделях вычислений полиномиально связаны» (Goldreich 2008, Глава 1.2). Это формирует основу для класса сложности P , который является набором задач принятия решений, решаемых детерминированной машиной Тьюринга за полиномиальное время. Соответствующий набор функциональных задач — FP . ${\displaystyle f(n)}$ ${\displaystyle \{xx\mid x{\text{ is any binary string}}\}}$

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

Представление отношения между классами сложности; L будет еще одним шагом «внутри» NL

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

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

Оказывается, PSPACE = NPSPACE и EXPSPACE = NEXPSPACE по теореме Сэвича .

Другие важные классы сложности включают BPP , ZPP и RP , которые определяются с помощью вероятностных машин Тьюринга ; AC и NC , которые определяются с помощью булевых схем; и BQP и QMA , которые определяются с помощью квантовых машин Тьюринга. #P — важный класс сложности задач подсчета (не задач принятия решений). Такие классы, как IP и AM, определяются с помощью интерактивных систем доказательств . ALL — класс всех задач принятия решений.

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

Для классов сложности, определенных таким образом, желательно доказать, что ослабление требований к (скажем) времени вычислений действительно определяет больший набор проблем. В частности, хотя DTIME( ) содержится в DTIME( ), было бы интересно узнать, является ли включение строгим. Для требований времени и пространства ответ на такие вопросы дается теоремами об иерархии времени и пространства соответственно. Они называются теоремами об иерархии, потому что они индуцируют надлежащую иерархию для классов, определенных ограничением соответствующих ресурсов. Таким образом, существуют пары классов сложности, такие, что один надлежащим образом включен в другой. Выведя такие надлежащие включения множеств, мы можем перейти к количественным утверждениям о том, насколько больше дополнительного времени или пространства необходимо для увеличения количества решаемых задач. ${\displaystyle n}$ ${\displaystyle n^{2}}$

Точнее, теорема об иерархии времени утверждает, что . ${\displaystyle {\mathsf {DTIME}}{\big (}o(f(n)){\big )}\subsetneq {\mathsf {DTIME}}{\big (}f(n)\cdot \log(f(n)){\big )}}$

Теорема о пространственной иерархии утверждает, что . ${\displaystyle {\mathsf {DSPACE}}{\big (}o(f(n)){\big )}\subsetneq {\mathsf {DSPACE}}{\big (}f(n){\big )}}$

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

Снижение

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

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

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

Если задача находится в и сложна для , то считается полной для . Это означает, что является самой сложной задачей в . (Поскольку многие задачи могут быть одинаково сложны, можно сказать, что это одна из самых сложных задач в .) Таким образом, класс NP-полных задач содержит самые сложные задачи в NP, в том смысле, что они, скорее всего, не находятся в P. Поскольку задача P = NP не решена, возможность свести известную NP-полную задачу, , к другой задаче, , будет означать, что не существует известного решения за полиномиальное время для . Это происходит потому, что решение за полиномиальное время для даст решение за полиномиальное время для . Аналогично, поскольку все задачи NP можно свести к множеству , нахождение NP-полной задачи, которая может быть решена за полиномиальное время, будет означать, что P = NP. ^[3] ${\displaystyle X}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle X}$ ${\displaystyle C}$ ${\displaystyle X}$ ${\displaystyle C}$ ${\displaystyle X}$ ${\displaystyle C}$ ${\displaystyle \Pi _{2}}$ ${\displaystyle \Pi _{1}}$ ${\displaystyle \Pi _{1}}$ ${\displaystyle \Pi _{1}}$ ${\displaystyle \Pi _{2}}$

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

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

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

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

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

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

Ладнер показал, что если то существуют задачи из , которые не являются ни в , ни -полными. ^[4] Такие задачи называются NP-промежуточными задачами. Задача изоморфизма графов , задача дискретного логарифма и задача факторизации целых чисел являются примерами задач, которые считаются NP-промежуточными. Они являются одними из немногих задач NP, о которых неизвестно, находятся ли они в или являются -полными. ${\displaystyle P\neq NP}$ ${\displaystyle NP}$ ${\displaystyle P}$ ${\displaystyle NP}$ ${\displaystyle P}$ ${\displaystyle NP}$

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

Задача факторизации целых чисел — это вычислительная задача определения простого множителя заданного целого числа. Формулируя ее как задачу принятия решений, это задача определения, имеет ли входной сигнал простой множитель, меньший . Эффективный алгоритм факторизации целых чисел неизвестен, и этот факт лежит в основе нескольких современных криптографических систем, таких как алгоритм RSA . Задача факторизации целых чисел находится в и в (и даже в UP и co-UP ^[11] ). Если задача является -полной, иерархия полиномиального времени схлопнется до своего первого уровня (т. е. будет равна ). Самым известным алгоритмом факторизации целых чисел является общее решето поля чисел , которому требуется время ^[12] для факторизации нечетного целого числа . Однако самый известный квантовый алгоритм для этой задачи, алгоритм Шора , работает за полиномиальное время. К сожалению, этот факт мало что говорит о том, где находится проблема относительно неквантовых классов сложности. ${\displaystyle k}$ ${\displaystyle NP}$ ${\displaystyle co{\text{-}}NP}$ ${\displaystyle NP}$ ${\displaystyle NP}$ ${\displaystyle co{\text{-}}NP}$ ${\displaystyle O(e^{\left({\sqrt[{3}]{\frac {64}{9}}}\right){\sqrt[{3}]{(\log n)}}{\sqrt[{3}]{(\log \log n)^{2}}}})}$ ${\displaystyle n}$

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

Предполагается, что многие известные классы сложности неравны, но это не доказано. Например , , но возможно, что . Если не равно , то не равно ни одному из них. Поскольку существует много известных классов сложности между и , таких как , , , , , , и т. д., возможно, что все эти классы сложности свернутся в один класс. Доказательство того, что любой из этих классов неравно, станет крупным прорывом в теории сложности. ${\displaystyle P\subseteq NP\subseteq PP\subseteq PSPACE}$ ${\displaystyle P=PSPACE}$ ${\displaystyle P}$ ${\displaystyle NP}$ ${\displaystyle P}$ ${\displaystyle PSPACE}$ ${\displaystyle P}$ ${\displaystyle PSPACE}$ ${\displaystyle RP}$ ${\displaystyle BPP}$ ${\displaystyle PP}$ ${\displaystyle BQP}$ ${\displaystyle MA}$ ${\displaystyle PH}$

В том же ключе, класс, содержащий дополнительные проблемы (т.е. проблемы с ответами «да» / «нет» в обратном порядке) проблем. Считается ^[13] , что не равно ; однако это еще не доказано. Ясно, что если эти два класса сложности не равны, то не равно , так как . Таким образом, если бы мы имели откуда . ${\displaystyle co{\text{-}}NP}$ ${\displaystyle NP}$ ${\displaystyle NP}$ ${\displaystyle co{\text{-}}NP}$ ${\displaystyle P}$ ${\displaystyle NP}$ ${\displaystyle P=co{\text{-}}P}$ ${\displaystyle P=NP}$ ${\displaystyle co{\text{-}}P=co{\text{-}}NP}$ ${\displaystyle NP=P=co{\text{-}}P=co{\text{-}}NP}$

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

Подозревается, что и равны. Однако в настоящее время он открыт, если . ${\displaystyle P}$ ${\displaystyle BPP}$ ${\displaystyle BPP=NEXP}$

Неразрешимость

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

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

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

Чтобы понять, почему алгоритмы с экспоненциальным временем обычно непригодны на практике, рассмотрим программу, которая выполняет операции перед остановкой. Для небольших , скажем, 100, и предположив для примера, что компьютер выполняет операции каждую секунду, программа будет работать около лет, что того же порядка, что и возраст Вселенной . Даже с гораздо более быстрым компьютером программа будет полезна только для очень маленьких случаев, и в этом смысле неразрешимость проблемы несколько независима от технологического прогресса. Однако алгоритм с экспоненциальным временем, который выполняет операции, практичен, пока не станет относительно большим. ${\displaystyle 2^{n}}$ ${\displaystyle n}$ ${\displaystyle 10^{12}}$ ${\displaystyle 4\times 10^{10}}$ ${\displaystyle 1.0001^{n}}$ ${\displaystyle n}$

Аналогично, алгоритм полиномиального времени не всегда практичен. Если его время выполнения, скажем, , то неразумно считать его эффективным, и он по-прежнему бесполезен, за исключением небольших случаев. Действительно, на практике даже алгоритмы или часто непрактичны для реалистичных размеров задач. ${\displaystyle n^{15}}$ ${\displaystyle n^{3}}$ ${\displaystyle n^{2}}$

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

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

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

История

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

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

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

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

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

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

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

• Сложность вычислений
• Описательная теория сложности
• Сложность игры
• Язык листьев
• Пределы вычислений
• Список классов сложности
• Список тем по вычислимости и сложности
• Список нерешенных проблем в информатике
• Параметризованная сложность
• Сложность доказательства
• Квантовая теория сложности
• Теория структурной сложности
• Трансвычислительная проблема
• Вычислительная сложность математических операций

Работает над сложностью

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

Ссылки

Цитаты

1. "P vs NP Problem | Clay Mathematics Institute". www.claymath.org . Архивировано из оригинала 6 июля 2018 г. . Получено 6 июля 2018 г. .
2. См. Arora & Barak 2009, Глава 1: Вычислительная модель и почему она не имеет значения.
3. См. Sipser 2006, Глава 7: Временная сложность
4. Ladner, Richard E. (1975), «О структуре полиномиальной приводимости по времени», Journal of the ACM , 22 (1): 151–171, doi : 10.1145/321864.321877 , S2CID  14352974.
5. Бергер, Бонни А.; Лейтон , Т. (1998), «Сворачивание белка в гидрофобно-гидрофильной (HP) модели является NP-полным», Журнал вычислительной биологии , 5 (1): 27–40, CiteSeerX 10.1.1.139.5547 , doi :10.1089/cmb.1998.5.27, PMID  9541869. 
6. Кук, Стивен (апрель 2000 г.), Проблема P против NP (PDF) , Clay Mathematics Institute , архивировано из оригинала (PDF) 12 декабря 2010 г. , извлечено 18 октября 2006 г.
7. Джаффе, Артур М. (2006), «Великий вызов тысячелетия в математике» (PDF) , Notices of the AMS , 53 (6), архивировано (PDF) из оригинала 12 июня 2006 г. , извлечено 18 октября 2006 г.
8. Арвинд, Викраман; Курур, Пиюш П. (2006), «Изоморфизм графов в SPP», Информация и вычисления , 204 (5): 835–852, doi :10.1016/j.ic.2006.02.002.
9. Шёнинг, Уве (1988), «Изоморфизм графов находится в низкой иерархии», Журнал компьютерных и системных наук , 37 (3): 312–323, doi :10.1016/0022-0000(88)90010-4
10. Бабай, Ласло (2016). «Изоморфизм графов за квазиполиномиальное время». arXiv : 1512.03547 [cs.DS].
11. Фортнау, Лэнс (13 сентября 2002 г.). «Блог о вычислительной сложности: факторизация». weblog.fortnow.com .
12. Wolfram MathWorld: Решето числового поля
13. Курс Боаза Барака по вычислительной сложности Лекция 2
14. Хопкрофт, Дж. Э., Мотвани, Р. и Ульман, Дж. Д. (2007) Введение в теорию автоматов, языки и вычисления , Addison Wesley, Бостон/Сан-Франциско/Нью-Йорк (стр. 368)
15. Мёрант, Жерар (2014). Алгоритмы и сложность . Elsevier. стр. 4. ISBN 978-0-08093391-7.
16. Зобель, Джастин (2015). Написание для Computer Science . Springer. стр. 132. ISBN 978-1-44716639-9.
17. Смейл, Стив (1997). «Теория сложности и численный анализ». Acta Numerica . 6. Cambridge Univ Press: 523–551. Bibcode : 1997AcNum...6..523S. CiteSeerX 10.1.1.33.4678 . doi : 10.1017/s0962492900002774. S2CID  5949193. 
18. Бабай, Ласло; Кампаньоло, Мануэль (2009). «Обзор вычислений в непрерывном времени». arXiv : 0907.3117 [cs.CC].
19. Томлин, Клэр Дж.; Митчелл, Ян; Байен, Александр М.; Ойши, Мико (июль 2003 г.). «Вычислительные методы проверки гибридных систем». Труды IEEE . 91 (7): 986–1001. CiteSeerX 10.1.1.70.4296 . doi :10.1109/jproc.2003.814621. 
20. Фортнау и Гомер (2003)
21. Ричард М. Карп, «Комбинаторика, сложность и случайность», лекция на вручении премии Тьюринга 1985 г.
22. Ямада, Х. (1962). «Вычисления в реальном времени и рекурсивные функции, невычислимые в реальном времени». Труды IEEE по электронным компьютерам . EC-11 (6): 753–760. doi :10.1109/TEC.1962.5219459.
23. Трахтенброт, Б. А.: Сигнализирующие функции и табличные операторы // Ученые записки Пензенского педагогического института, 1956, т. 4, с. 75–87.
24. Борис Трахтенброт, «От логики к теоретической информатике – обновление». В: Столпы компьютерной науки , LNCS 4800, Springer 2008.
25. Ричард М. Карп (1972), «Сводимость среди комбинаторных проблем» (PDF) , в RE Miller; JW Thatcher (ред.), Complexity of Computer Computations , Нью-Йорк: Plenum, стр. 85–103, архивировано из оригинала (PDF) 29 июня 2011 г. , извлечено 28 сентября 2009 г.

Учебники

• Арора, Санджив ; Барак, Боаз (2009), Вычислительная сложность: современный подход, Cambridge University Press, ISBN 978-0-521-42426-4, Збл  1193.68112
• Дауни, Род; Феллоуз, Майкл (1999), Параметризованная сложность , Монографии по информатике, Берлин, Нью-Йорк: Springer-Verlag, ISBN 9780387948836
• Ду, Дин-Чжу; Ко, Кер-И (2000), Теория вычислительной сложности , John Wiley & Sons, ISBN 978-0-471-34506-0
• Garey, Michael R .; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455. MR  0519066. OCLC  247570676.
• Голдрайх, Одед (2008), Вычислительная сложность: концептуальная перспектива, Cambridge University Press
• ван Лиувен, Ян , ред. (1990), Справочник по теоретической информатике (т. A): алгоритмы и сложность , MIT Press, ISBN 978-0-444-88071-0
• Пападимитриу, Христос (1994), Computational Complexity (1-е изд.), Addison Wesley, ISBN 978-0-201-53082-7
• Сипсер, Майкл (2006), Введение в теорию вычислений (2-е изд.), США: Thomson Course Technology, ISBN 978-0-534-95097-2

Опросы

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

Внешние ссылки

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