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


Из Википедии, свободной энциклопедии

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

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

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

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

Коммивояжером тур по 14 городам Германии.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

меры Сложностные

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

класс сложности Модель вычислений ограничение ресурсов
Детерминированный время
DTIME ( е ( п )) Детерминированный машин Тьюринга Время е ( п )
     
п Детерминированный машин Тьюринга Время поли ( п )
EXPTIME Детерминированный машин Тьюринга Время 2 поли ( п )
Недетерминированные время
Ntime ( е ( п )) Недетерминированная машина Тьюринга Время е ( п )
     
NP Недетерминированная машина Тьюринга Время поли ( п )
NEXPTIME Недетерминированная машина Тьюринга Время 2 поли ( п )
класс сложности Модель вычислений ограничение ресурсов
Детерминированное пространство
DSPACE ( е ( п )) Детерминированный машин Тьюринга Пространство F ( п )
L Детерминированный машин Тьюринга Пространство O (журнал N )
PSPACE Детерминированный машин Тьюринга Пространство поли ( п )
EXPSPACE Детерминированный машин Тьюринга Пространство 2 поли ( п )
Недетерминированные пространство
N-Space ( е ( п )) Недетерминированная машина Тьюринга Пространство F ( п )
NL Недетерминированная машина Тьюринга Пространство O (журнал N )
NPSPACE Недетерминированная машина Тьюринга Пространство поли ( п )
NEXPSPACE Недетерминированная машина Тьюринга Пространство 2 поли ( п )

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

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

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

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

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

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

,

Теорема пространства иерархии гласит , что

,

Теоремы иерархии времени и пространства, образуют основу для большинства результатов разделения классов сложности. Например, теорема времени иерархия говорит нам, что 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-полных задач содержит самые сложные проблемы в НП, в том смысле , что они являются те , скорее всего , не быть в P. Поскольку проблема P = NP не решена, будучи в состоянии уменьшить известную NP-полной задачи, Π 2 , к другой проблеме, Π 1 , будет означать , что не существует никакого известного полиномиальное время решения для П 1 . Это потому , что полином время решения к П 1 , будет образовывать полиномиальное время решения П 2 . Аналогичным образом , поскольку все проблемы , NP может быть сведена к набору, находя NP-полную проблему , которая может быть решена за полиномиальное время будет означать , что P = NP.

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

Диаграмма классов сложности при условии, что P ≠ NP. Наличие проблем в NP вне как P и NP-полной в этом случае было установлено Ladner.

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

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

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

Проблемы в НП не известно, что в P или NP-полной

Было показано , что если Ladner РNP , то существуют проблемы в НП , которые ни в Р , ни НП-полной . Такие задачи называются NP-промежуточные проблемы. Проблема изоморфизма графов , то дискретное логарифмирование и целочисленная задача факторизации являются примерами проблем , которые считаются NP-промежуточное соединением. Они являются одними из немногих проблем NP не известно, в P или быть NP-полным .

Проблема изоморфизма графов является вычислительной задачей определения , является ли две конечными графами являются изоморфными . Важная нерешенная проблема в теории сложности , является ли проблема изоморфизма графов в P , NP-полный , или NP-интермедиат. Ответ не известен, но считается , что проблема по крайней мере , не NP-полной. Если изоморфизм графов является NP-полным, то полиномиальная иерархия времени падает на ее второй уровень. Поскольку широко распространено мнение , что многочлен иерархия не разрушится до любого конечного уровня, то считается , что изоморфизм графов не является NP-полным. Лучший алгоритм для решения этой проблемы в связи с Ласло Бабая и Евгений Luks побежал время для графов с п вершинами, хотя некоторые недавние работы по Бабая предлагает некоторые потенциально новые перспективы на этом.

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

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

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

В том же ключе, со-NP класс , содержащий комплементарные проблемы (то есть проблемы с да / нет ответов не наоборот) из НП проблем. Считается , что NP не равны совместно NP ; Однако, это еще не доказано. Совершенно очевидно , что если эти два класса сложности не равны , то P не равно NP , так как если P = NP мы также имеем P = со-NP , так как проблемы в НП двойственны тем в сотрудничестве НП . Неясно.

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

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

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

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

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

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

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

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

история

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

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

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

Ранние работы , изучающие проблемы разрешимы машинами Тьюринга с определенными ограниченными ресурсами , включают Джон Myhill «определение s из линейных ограниченных автоматов (Myhill 1960), Смаллиан » s исследование рудиментарных множеств (1961), а также Хисао Ямада бумаги «s на вещественно время вычисления (1962). Несколько ранее, Трахтенброт (1956), пионер в области из СССР, изучал другую специфическую меру сложности. Как он вспоминает:

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

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

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

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

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

Цитирование

учебники

Обзоры

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