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

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

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

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

Вычислительные проблемы [ править ]

Проблемные экземпляры [ править ]

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

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

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

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

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

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

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

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

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

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

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

Измерение размера экземпляра [ править ]

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

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

Модели машин и меры сложности [ править ]

Машина Тьюринга [ править ]

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

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

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

Другие модели машин [ править ]

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

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

Меры сложности [ править ]

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

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

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

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

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

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

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

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

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

Верхняя и нижняя оценки сложности задач [ править ]

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

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

Классы сложности [ править ]

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

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

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

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

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

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

Важные классы сложности [ править ]

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

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

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

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

Теоремы об иерархии [ править ]

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

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

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

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

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

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

Сокращение [ править ]

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

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

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

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

Важные открытые проблемы [ править ]

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

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

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

Проблемы в NP не известны ни в P, ни в NP-Complete [ править ]

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

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

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

Разделение между другими классами сложности [ править ]

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

Аналогичным образом, co-NP - это класс, содержащий проблемы дополнения (то есть проблемы с обратными ответами « да / нет» ) проблем NP . Считается ^[13], что 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 .

Несговорчивость [ править ]

Найдите послушный , выполнимый , трудноразрешимый или невыполнимый в Wiktionary, бесплатный словарь.

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

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

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

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

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

Теория непрерывной сложности [ править ]

Теория непрерывной сложности может относиться к теории сложности задач, которые включают непрерывные функции, аппроксимируемые дискретизацией, как это изучается в численном анализе . Один из подходов к теории сложности численного анализа ^[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]

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

См. Также [ править ]

Работает по сложности [ править ]

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

Ссылки [ править ]

Цитаты [ править ]

Учебники [ править ]

• Арора, Санджив ; Барак, Боаз (2009), Вычислительная сложность: современный подход , Cambridge University Press, ISBN 978-0-521-42426-4, Zbl  1193,68112
• Дауни, Род; Стипендиаты, Майкл (1999), Параметризованная сложность , Монографии по компьютерным наукам, Берлин, Нью-Йорк: Springer-Verlag, ISBN 9780387948836
• Ду, Дин-Чжу; Ко, Кер-I (2000), Теория вычислительной сложности , John Wiley & Sons, ISBN 978-0-471-34506-0
• Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , У. Х. Фриман , ISBN 0-7167-1045-5
• Голдрайх, Одед (2008), Вычислительная сложность: концептуальная перспектива , Cambridge University Press
• ван Леувен, Ян , изд. (1990), Справочник по теоретической информатике (том A): алгоритмы и сложность , 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

Опросы [ править ]

• Халил, Хатем; Ulery, Дана (1976), «Обзор текущих исследований по сложности алгоритмов для дифференциальных уравнений в частных» , Труды ежегодной конференции по - АКМ 76 , АКМ '76: 197-201, DOI : 10,1145 / 800191,805573 , S2CID  15497394
• Кук, Стивен (1983), "Обзор вычислительной сложности" (PDF) , Commun. ACM , 26 (6): 400–408, doi : 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 , doi : 10.1109 / 5992.998639 , ISSN  1521-9615 , S2CID  633346

Внешние ссылки [ править ]

Викискладе есть медиафайлы, связанные с теорией вычислительной сложности .

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