Я пытаюсь понять эти классификации и почему они существуют. Правильно ли мое понимание? Если нет, то что?

1. P - полиномиальная сложность, или для некоторого неотрицательного действительного числа , такого как , и т. Д. Если проблема принадлежит P, то существует по крайней мере один алгоритм, который может решить ее с нуля за полиномиальное время. Например, я всегда могу выяснить, является ли какое-то целое число простым, перебирая и проверяя на каждом шаге деление .O(nk)kO(1), O(n1/2), O(n2), O(n3)n2 <= k <= sqrt(n)kn

2. NP - недетерминированная полиномиальная сложность. Я действительно не знаю, что значит быть недетерминированным. Я думаю, это означает, что это легко проверить за полиномиальное время, но может или не может быть полиномиальным временем, чтобы решить с нуля, если мы еще не знали ответ. Поскольку это может быть решено за полиномиальное время, все P-проблемы также являются NP-задачами. Целочисленная факторизация приводится в качестве примера NP, но я не понимаю, почему это не P лично, поскольку пробная факторизация требует O(sqrt(n))времени.

3. NP-Complete Я совсем не понимаю, но в качестве примера приводится проблема коммивояжера. Но, на мой взгляд, проблемой TSP может быть только NP, потому что требуется что-то вроде проверки, если вам дали путь вперед.O(2n n2) time to solve, but O(n)

4. NP-Hard, я полагаю, просто полон неизвестных. Трудно проверить, трудно решить.

Вы в основном правы относительно P и NP, но не про NP-hard и NP-complete.

Для начала приведем краткие определения четырех рассматриваемых классов сложности:

• P - класс задач решения, которые могут быть решены за полиномиальное время детерминированной машиной Тьюринга.

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

• NP-hard - это класс задач решения, к которому все проблемы в NP могут быть сведены до полиномиального времени с помощью детерминированной машины Тьюринга.

• NP-complete - это пересечение NP-hard и NP. Эквивалентно, NP-полная - это класс задач решения в NP, к которому все проблемы в NP могут быть сведены до полиномиального времени с помощью детерминированной машины Тьюринга.

А вот диаграмма Эйлера из Википедии, показывающая отношения между этими четырьмя классами (при условии, что P не равен NP):

Часть, которая, как я полагаю, вам наиболее незнакома или смущена, - это понятие «сокращения полиномиального времени» от проблемы X к проблеме Y. Сокращение от X до Y - это просто алгоритм A, который решает X, используя некоторые другой алгоритм B, который решает проблему Y. Это сокращение называется «сокращением полиномиального времени», если все части A, кроме B, имеют сложность полиномиального времени. В качестве тривиального примера проблема поиска наименьшего элемента в массиве сводится к задаче сортировки с постоянным временем, поскольку вы можете отсортировать массив и затем вернуть первый элемент отсортированного массива.

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

Проблема остановки - хороший пример NP-трудной проблемы, которой явно нет в NP, как объясняет Википедия :

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

Целочисленная факторизация приведена в качестве примера NP, но я не понимаю, почему это не P лично, поскольку пробная факторизация занимает O (sqrt (n)) время.

Для целей классов сложности, nдлина ввода. Так что если вы хотите фактор целого числа k, nне kно log k, число бит (или любой другой ) , что требуется , чтобы записать номер. Таким образом, целочисленная факторизация, O(sqrt(k))как вы говорите, но это то, что есть .O(sqrt(2n))O(2(n/2))

NP-Hard, я полагаю, просто полон неизвестных. Трудно проверить, трудно решить.

Нет. NP-Hard просто о том, как трудно решить проблему.

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

NP-Complete Я вообще не понимаю

NP-Complete означает, что проблема является как NP, так и NP-Hard. Это означает, что мы можем быстро проверить решение (NP), но это по крайней мере так же сложно, как самая сложная проблема в NP (NP-Hard).

Я действительно не знаю, что значит быть недетерминированным.

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

Первое, что нужно понять, это то, что P и NP классифицируют языки , а не проблемы . Чтобы понять, что это значит, сначала нам понадобятся другие определения.

Алфавит является непустым конечным множеством символов.

{ 0, 1} алфавит, как и набор символов ASCII. {} не алфавит, потому что он пуст. N (целые числа) не алфавит, потому что он не конечен.

Пусть Σ - алфавит. Упорядоченная конкатенация конечного числа символов из Σ называется словом над Σ .

Строка 101- это слово над алфавитом { 0, 1}. Пустое слово (часто пишется как е ) слово над любым алфавитом. Строка penguin- это слово в алфавите, содержащее символы ASCII. Десятичная запись числа Пи не слово в алфавите { ., 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} , потому что это не является конечным.

Длина слова ш , записывается в виде | w |, количество символов в нем.

Например, | hello| = 5 и | ε | = 0. Для любого слова w , | ш | ∈ N и, следовательно, конечно.

Пусть Σ - алфавит. Множество Σ ^＊ содержит все слова над Σ , включая ε . Множество Σ ⁺ содержит все слова над Σ , кроме ε . Для п ∈ N , Σ ^п является множество слов длины п .

Для каждого алфавита Σ , Σ ^＊ и Σ ⁺ являются бесконечными счетными множествами . Для набора символов ASCII Σ _ASCII регулярные выражения .*и .+обозначают Σ _ASCII ^＊ и Σ _ASCII ⁺ соответственно.

{ 0, 1} ⁷ является набор 7-битовых кодов ASCII { 0000000, 0000001..., 1111111}. { 0, 1} ³² - это набор 32-битных целочисленных значений.

Пусть Σ - алфавит и L ⊆ Σ ^＊ . L называется языком над Σ .

Для алфавита Σ пустое множество и Σ ^＊ являются тривиальными языками над Σ . Первый часто называют пустым языком . Пустой язык {} и язык, содержащий только пустое слово { ε }, различны.

Подмножество { 0, 1} ^32, которое соответствует не-NaN значениям IEEE 754 с плавающей запятой, является конечным языком.

Языки могут иметь бесконечное количество слов, но каждый язык исчисляется. Множество строк { 1, 2...} , обозначающая целые числа в десятичной системе счисления бесконечного язык над алфавитом { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Бесконечное множество цепочек { 2, 3, 5, 7, 11, 13, ...} , обозначающий простые числа в десятичной системе счисления является собственным подмножеством их. Язык, содержащий все слова, соответствующие регулярному выражению, [+-]?\d+\.\d*([eE][+-]?\d+)?является языком над набором символов ASCII (обозначающим подмножество допустимых выражений с плавающей запятой, как определено языком программирования C).

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

Пусть Σ - алфавит и L ⊆ Σ ^＊ . Машина D решает , L , если для каждого входа ш ∈ Е ^* он вычисляет характеристическую функцию х _L ( ш ) в конечное время. Характеристическая функция определяется как

χ л : Σ * → {0, 1}
     ш   ↦ 1,   ш ∈ L 
         0, в противном случае.

Такая машина называется решающей для L . Мы пишем « D ( w ) = x » для «данного w , D выводит x ».

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

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

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

Поскольку вы использовали его в своем вопросе, я предполагаю, что вы уже знакомы с нотацией «большой-O», так что здесь только быстрое освежение.

Пусть f : N → функция. Множество O ( f ) содержит все функции g : N → N, для которых существуют постоянные n ₀ ∈ N и c ∈ N такие, что для каждого n ∈ N при n > n ₀ верно, что g ( n ) ≤ c f ( н ).

Теперь мы готовы подойти к реальному вопросу.

Класс Р содержит все языки L , для которого существует машина Тьюринга D , который решает L и константа K ∈ N такое , что для каждого входа ш , D останавливается после того, как в большинстве Т (| ш |) шагов для функции Т ∈ O ( n ↦ n ^k ).

Поскольку O ( n ↦ n ^k ), хотя математически правильно, неудобно писать и читать, большинство людей, если честно, все, кроме меня, обычно пишут просто O ( n ^k ).

Обратите внимание, что оценка зависит от длины w . Следовательно, аргумент, который вы задаете для языка простых чисел, верен только для чисел в unaray кодировках , где для кодировки w числа n длина кодировки | ш | пропорционально п . Никто бы никогда не использовал такую ​​кодировку на практике. Используя более продвинутый алгоритм, чем просто пробуя все возможные факторы, можно показать, однако, что язык простых чисел остается в P, если входные данные закодированы в двоичном формате (или в любой другой базе). (Несмотря на огромный интерес, это могли доказать только Маниндра Агравал, Нирадж Каял и Нитин Саксена в удостоенной наград бумаге в 2004 году, так что вы можете догадаться, что алгоритм не очень прост.)

Тривиальные языки {} и Σ ^＊ и нетривиальный язык { ε }, очевидно, находятся в P (для любого алфавита Σ ). Можете ли вы написать функции на вашем любимом языке программирования, которые принимают строку в качестве входных данных и возвращают логическое значение, указывающее, является ли строка словом из языка для каждого из них, и доказывает, что ваша функция имеет полиномиальную сложность во время выполнения?

Каждый регулярный язык (язык описывается регулярным выражением) в P .

Пусть Σ - алфавит и L ⊆ Σ ^＊ . Машина V, которая принимает закодированный кортеж из двух слов w , c ∈ Σ ^＊ и выдает 0 или 1 после конечного числа шагов, является верификатором для L, если она имеет следующие свойства.

• Принимая во внимание ( ш , с ), V выходы 1 только тогда , когда W ∈ L .
• Для любого w ∈ L существует такое c ∈ Σ ^＊ , что V ( w , c ) = 1.

С в приведенном выше определении, называется свидетелем (или сертификат ).

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

Для языка COMPOSITE, который содержит десятичные кодировки всех целых чисел, которые не являются простыми, свидетель может быть факторизацией. Например, (659, 709)является свидетелем для 467231∈ COMPOSITE. Вы можете легко проверить, что на листе бумаги, не имея свидетеля, доказать, что 467231 не является простым, было бы трудно без использования компьютера.

Мы ничего не сказали о том, как найти подходящего свидетеля. Это недетерминированная часть.

Класс NP содержит все языки L, для которых существует машина Тьюринга V, которая проверяет L, и постоянную k ∈ N такую, что для каждого входа ( w , c ) V останавливается после не более чем T (| w |) шагов для функции T ∈ O ( n ↦ n ^k ).

Отметим, что из приведенного выше определения следует, что для каждого w ∈ L существует свидетель c с | с | ≤ T (| w |). (Машина Тьюринга не может видеть больше символов свидетеля.)

NP является надмножеством P (почему?). Неизвестно , существуют ли языки, которые в NP , но не в P .

Целочисленная факторизация не является языком как таковым. Однако мы можем построить язык, который представляет проблему решения, связанную с ним. То есть язык, который содержит все кортежи ( n , m ), для которых n имеет множитель d с d ≤ m . Давайте назовем этот язык ФАКТОРОМ. Если у вас есть алгоритм для выбора FACTOR, его можно использовать для вычисления полной факторизации только с полиномиальными издержками, выполняя рекурсивный двоичный поиск для каждого простого фактора.

Нетрудно показать, что ФАКТОР находится в НП . Подходящим свидетелем будет просто сам фактор d , и все, что должен сделать верификатор, это убедиться, что d ≤ m и n mod d = 0. Все это можно сделать за полиномиальное время. (Помните, опять же, что учитывается длина кодировки , которая логарифмична по n .)

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

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

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

Пусть Σ - алфавит, а A и B - языки над Σ . Является полиномиальное время многих один приводимым к B , если существует функция F : Σ ^* → Σ ^* со следующими свойствами.

• w ∈ A   ⇔   f ( w ) ∈ B   для всех w ∈ Σ ^＊ .
• Функция f может быть вычислена машиной Тьюринга для каждого входа w за несколько шагов, ограниченных полиномом из | ш |

В этом случае мы пишем ≤ _р B .

Например, пусть A будет языком, который содержит все графы (закодированные как матрица смежности), которые содержат треугольник. (Треугольник - это цикл длины 3.) Пусть далее B будет языком, который содержит все матрицы с ненулевым следом. (След матрицы является суммой его основных диагональных элементов.) Тогда полиномиален многие один сводится к B . Чтобы доказать это, нам нужно найти подходящую функцию преобразования f . В этом случае мы можем установить f для вычисления ^{третьей} степени матрицы смежности. Это требует двух матрично-матричных произведений, каждое из которых имеет полиномиальную сложность.

Это тривиально верно , что L ≤ _р л . (Вы можете доказать это формально?)

Мы применим это к NP сейчас.

Язык L является NP- трудным тогда и только тогда, когда L '≤ _p L для каждого языка L ' ∈ NP .

An NP -Жесткого языка может или не может быть в НП сам.

Язык L является NP- завершенным тогда и только тогда, когда

• L ∈ NP и
• L является NP- жестким.

Самый известный NP- полный язык - это SAT. Он содержит все логические формулы, которые могут быть выполнены. Например, ( a ∨ b ) ∧ (¬ a ∨ ¬ b ) ∈ SAT. Действительный свидетель - { a = 1, b = 0}. Формула ( a ∨ b ) ∧ (¬ a ∨ b ) ∧ ¬ b ∉ SAT. (Как бы вы это доказали?)

Нетрудно показать, что SAT ∈ NP . Чтобы показать NP- твердость SAT - это некоторая работа, но она была сделана в 1971 году Стивеном Куком .

После того, как этот один NP- полный язык был известен, было относительно просто показать NP- полноту других языков посредством сокращения. Если язык , как известно, NP -трудной, то показывая , что ≤ _р B показывает , что B является NP -трудной тоже (через транзитивность «≤ _р »). В 1972 году Ричард Карп опубликовал список из 21 языка, который он мог показать как NP -полное (транзитивное) сокращение SAT. (Это единственная статья в этом ответе, которую я на самом деле рекомендую вам прочитать. В отличие от других, ее нетрудно понять, и она дает очень хорошее представление о том, как работает доказательство полноты NP посредством сокращения.)

Наконец, краткое резюме. Мы будем использовать символы NPH и NPC для обозначения классов языков NP- hard и NP- complete, соответственно.

• P ⊆ NP
• NPC ⊂ NP и NPC ⊂ NPH , фактически NPC = NP ∩ NPH по определению
• ( A ∈ NP ) ∧ ( B ∈ NPH ) ⇒   A ≤ _p B

Заметим, что включение NPC ⊂ NP является правильным даже в случае, когда P = NP . Чтобы убедиться в этом, проясните, что ни один нетривиальный язык не может быть сведен к тривиальному, и в P есть тривиальные языки, а в NP - нетривиальные языки . Это (не очень интересный) угловой случай.

добавление

Ваш основной источник путаницы, по-видимому, состоит в том, что вы думали о « n » в « O ( n ↦ f ( n ))» как о интерпретации входных данных алгоритма, когда они фактически ссылаются на длину входных данных. Это важное различие, потому что это означает, что асимптотическая сложность алгоритма зависит от кодировки, используемой для ввода.

На этой неделе был достигнут новый рекорд крупнейшего известного пика Мерсенна . Самое большое известное в настоящее время простое число - 2 ^{74 207 281} - 1. Это число настолько велико, что вызывает головную боль, поэтому я буду использовать меньшее в следующем примере: 2 ³¹ - 1 = 2 147 483 647. Это может быть закодированы по-разному.

• по показателю Мерсенна в виде десятичного числа: 31(2 байта)
• как десятичное число: 2147483647(10 байтов)
• в виде одинарного числа: 11111…11где …необходимо заменить еще 2 147 483 640 1с (почти 2 ГиБ)

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

Наивный алгоритм тестирования простоты является полиномиальным только для унарных кодировок. Тест простоты AKS является полиномиальным для десятичной (или любой другой базы b ≥ 2). Тест примитивности Лукаса-Лемера является наиболее известным алгоритмом для простых чисел Мерсенна M _p с p нечетным простым числом, но он все еще экспоненциально по длине двоичного кодирования показателя Мерсенна p (многочлен от p ).

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

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

Для некоторых задач, для которых язык решений в двоичном кодировании является NP- полным, язык решений больше не является NP- полным, если кодирование встроенных чисел переключено на унарное. Языки решений для других задач остаются NP- полными даже тогда. Последние называются сильно NP- полными . Самый известный пример - упаковка бина .

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

В 1983 году Хана Гальперин и Ави Вигдерсон написали интересную статью о сложности общих алгоритмов графа, когда входное кодирование графа сжато логарифмически. Для этих входных данных язык графов, содержащий треугольник сверху (где это было ясно в P ), внезапно становится NP- полным.

И это потому, что языковые классы, такие как P и NP , определены для языков , а не для проблем .

Я постараюсь дать вам менее неформальное определение для того же.

P проблемы: проблемы, которые могут быть решены за полиномиальное время. Содержит проблемы, которые могут быть эффективно решены.

Проблема NP: проблемы, которые можно проверить за полиномиальное время. Например: коммивояжёр, схемотехника. Проблемы с NP похожи на головоломки (например, на судоку). При правильном решении проблемы мы можем очень быстро проверить наше решение, но если мы на самом деле пытаемся решить его, это может занять вечность.

Теперь P vs NP на самом деле спрашивает, есть ли проблема, решение которой может быть быстро проверено на правильность, тогда всегда есть быстрый способ ее решения. Таким образом, писать математически: NP - это подмножество P или нет?

Теперь вернемся к завершению NP: это действительно сложные проблемы NP. Поэтому, если есть более быстрый способ выполнить NP NPC, NP NPC становится P, а проблемы NP превращаются в P.

NP hard: проблемы, которые невозможно проверить даже за полиномиальное время, np hard. Например, выбор лучшего хода в шахматах - один из них.

Если что-то неясно, попробуйте посмотреть это видео: https://www.youtube.com/watch?v=YX40hbAHx3s

Я надеюсь, что это обеспечит размытый контур.