Объяснение теории вычислительной сложности
https://stackoverflow.com/questions/308213
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Предполагая некоторое знание математики, как бы вы дали наивным общий обзор теории вычислительной сложности?
Я ищу объяснение вопроса о P = NP.Что такое P?Что такое NP?Что такое NP-Жесткий диск?
Иногда Википедия пишется так, как будто читатель уже понимает все используемые концепции.
Решение
Ууууу, докторский аккомпанемент. Хорошо, здесь идет.
Мы начнем с идеи решения проблемы, задачи, для которой алгоритм всегда может ответить "да" или "нет". Нам также нужна идея двух моделей компьютера (на самом деле, машины Тьюринга): детерминированной и недетерминированной. Детерминированный компьютер - это обычный компьютер, о котором мы всегда думаем; недетерминированный компьютер - это тот компьютер, к которому мы привыкли, за исключением того, что он имеет неограниченный параллелизм, поэтому каждый раз, когда вы приходите на ветку, вы запускаете новый «процесс». и осмотрите обе стороны. Как сказал Йоги Берра, когда вы приходите к развилке на дороге, вы должны взять ее.
Решение проблемы в P, если существует известный алгоритм за полиномиальное время, чтобы получить этот ответ. Решение проблемы в NP, если для недетерминированной машины есть известный алгоритм полиномиального времени, чтобы получить ответ.
Проблемы, о которых известно, что они находятся в P, тривиальны в NP - недетерминированная машина просто никогда не беспокоится о том, чтобы разветвлять другой процесс, и действует как детерминистская. Есть проблемы, о которых известно, что их нет ни в P, ни в NP; простой пример - перечислить все битовые векторы длины n. Независимо от того, что это занимает 2 n шагов.
(Строго говоря, проблема решения в NP, если нодерминистская машина может прийти к ответу за многократное время, а детерминированная машина может проверить , что решение является правильным за много времени.)
Но есть некоторые проблемы, о которых известно, что они существуют в NP, для которых не известен детерминистический алгоритм, работающий по принципу поли-времени; Другими словами, мы знаем, что они в NP, но не знаем, есть ли они в P. Традиционным примером является версия задачи о решении задачи коммивояжера (TSP): учитывая города и расстояния, есть ли маршрут, который охватывает все города, возвращаясь к начальной точке, на расстоянии менее чем x ? Легко в недетерминированной машине, потому что каждый раз, когда недетерминированный коммивояжер приходит на развилку дороги, он берет его: его клоны направляются в следующий город, который они не посетили, и в конце они сравнивают записи и смотрят, любой из клонов занимал расстояние менее чем x .
(Тогда экспоненциально много клонов борются за это, за что должны быть убиты.)
Неизвестно, находится ли TSP для принятия решения в P: не существует известного решения с разным временем, но нет никаких доказательств того, что такого решения не существует.
Теперь, еще одна концепция: учитывая задачи решения P и Q, если алгоритм может преобразовать решение для P в решение для Q за полиномиальное время, говорят, что Q является сокращаемым по времени (или просто сводится) к P.
Задача является NP-полной, если вы можете доказать, что (1) она находится в NP, и (2) показать, что она за многократное время сводится к задаче, уже известной как NP-полная. (Сложной частью этого было обеспечить первый пример проблемы с NP-завершением: это было сделано Стивом Куком в Теорема Кука .)
На самом деле, это говорит о том, что если кто-то когда-нибудь найдет решение по времени с одной проблемой NP-complete, он автоматически получит его для всех задач NP-complete; это также будет означать, что P = NP.
Проблема является NP-сложной, если и только если она " по крайней мере, как " трудно как NP-полная проблема. Более обычный коммивояжёр. Задача поиска кратчайшего маршрута - сложная, а не полная.
Другие советы
Майкл Сипсер Введение в теорию вычислений - отличная книга, и она очень читабельна. Другим отличным ресурсом является Скотт Ааронсон. Идеи в курсе теоретической информатики .
Формализм, который используется, состоит в том, чтобы рассматривать проблемы решения (проблемы с ответом Да / Нет, например "имеет ли этот граф гамильтонов цикл") как "языки" - наборы строк - входные данные, для которых ответ «Да». Существует формальное представление о том, что такое «компьютер». is (машина Тьюринга), и проблема в P, если есть алгоритм полиномиального времени для решения этой проблемы (с учетом входной строки, скажем, да или нет) на машине Тьюринга.
Проблема в NP, если он проверяемый за полиномиальное время, т. е. если для входных данных, где ответ Да, существует сертификат (полиномиального размера), который вы можете проверить, что ответ да в полиномиальное время. [Например. учитывая гамильтонов цикл в качестве сертификата, вы, очевидно, можете проверить, что он один.]
В нем ничего не говорится о том, как найти этот сертификат. Очевидно, вы можете попробовать «все возможные сертификаты» но это может занять экспоненциальное время; неясно, всегда ли у будет тратить больше, чем полиномиальное время, чтобы решить, да или нет; это вопрос P против NP.
Проблема NP-сложна, если ее решение означает возможность решить все проблемы в NP.
Также посмотрите этот вопрос: Что такое NP-полная в информатике?
Но на самом деле, все это, вероятно, только неопределенно для вас; стоит потратить время на прочтение, например Книга Сипсера. Это прекрасная теория.
Это комментарий к сообщению Чарли.
Проблема является NP-полной, если вы можете доказать, что (1) она находится в NP, и (2) показать, что оно сводится по времени к проблеме, уже известной быть NP-завершенным.
Со вторым условием есть небольшая ошибка. На самом деле, вам нужно доказать, что известная NP-полная проблема (скажем, Y ) сводится к этой проблеме за полиномиальное время (назовем ее проблемой X ).
Причиной такого способа доказательства является то, что если вы могли бы уменьшить проблему NP -Complete до этой проблемы и каким-то образом решить ее в поли-времени, то вы также преуспели в найти решение по времени для решения проблемы NP , что было бы замечательно (если не невозможно), поскольку с тех пор вам удастся решить давнюю P = NP проблема.
Еще один способ взглянуть на это доказательство состоит в том, что он использует метод контра-позитивного доказательства, который по существу утверждает, что если Y - > X , затем ~ X - > ~ Y . Другими словами, невозможность решить Y за полиномиальное время невозможна, значит также не решить X за многократное время. С другой стороны, если вы можете решить X в поли-времени, то вы также можете решить Y в поли-времени. Кроме того, вы можете решить все проблемы, которые сводятся к Y в поли-времени, а также транзитивности.
Я надеюсь, что мое объяснение выше достаточно ясно. Хорошим источником является Глава 8 Разработка алгоритма Кляйнберга и Тардоса или Глава 34 Кормена и др.
К сожалению, две лучшие из известных мне книг ( Гэри и Джонсон и Хопкрофт и Уллман ) оба начинаются с уровня, ориентированного на выпускников математика. Это почти наверняка необходимо, так как весь вопрос очень легко неправильно понять или исказить. Джеффу чуть не откусили уши , когда он тоже попытался подойти к этому вопросу. народный / шутка тон.
Возможно, лучший способ - это просто выполнить большую практическую работу с нотацией big-O используя множество примеров и упражнений . См. Также этот ответ . Однако обратите внимание, что это не совсем одно и то же: отдельные алгоритмы могут быть описаны асимптотами, но утверждение, что проблема имеет определенную сложность, является утверждением о каждом возможном алгоритме для этого. Вот почему доказательства так сложны!
Я помню " вычислительную сложность " от Пападимитриу (надеюсь, я правильно написал имя) как хорошая книга
очень упрощенно: проблема NP-трудна, если единственный способ ее решить - перечислить все возможные ответы и проверить каждый из них.
Вот несколько ссылок на эту тему:
Если вы знакомы с идеей мощности множества, то есть количества элементов в наборе, тогда можно было бы рассматривать вопрос как P, представляющий мощность целых чисел, в то время как NP является загадкой:Это одно и то же или оно больше, как мощность всех действительных чисел?
Мой упрощенный ответ: «Сложность вычислений - это анализ того, насколько сложнее становится проблема, когда вы добавляете больше элементов».
В этом предложении слово «сложнее» является намеренно расплывчатым, поскольку может относиться либо ко времени обработки, либо к использованию памяти.
В информатике недостаточно решить проблему. Это должно быть решаемо в разумные сроки. Таким образом, в то время как в чистой математике вы придумываете уравнение, в CS вы должны уточнить это уравнение, чтобы вы могли решить задачу в разумные сроки.
Это самый простой способ, который я могу представить, это может быть слишком просто для ваших целей.
В зависимости от того, сколько у вас есть времени, возможно, было бы лучше начать с DFA, NDFA, а затем показать, что они эквивалентны. Тогда они понимают ND и D и будут лучше понимать регулярные выражения как хороший побочный эффект.
