Мотивация использования карп-редукций в теории

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

Тем не менее, в теории -полнота, понятие N P -hardness захватывается с помощью сокращений (сокращения отображения Karp). Эта концепция «ограниченных» сокращений гораздо менее интуитивна (по крайней мере, для меня). Это даже кажется немного надуманным, поскольку создает несколько менее интуитивное представление о твердости; с тем , что я имею в виду тот факт , что N P не содержит тривиальным гр уплотнительное - N P . Хотя в теории сложности мы очень привыкли к концепции, что возможность решить такую ​​проблему, как S A T , не означает, что мы можем решить ¯ S A $\mathcal{NP}$$\mathcal{NP}$$\mathcal{NP}$$co-\mathcal{NP}$$\mathsf{SAT}$$\overline{\mathsf{SAT}}$В естественных условиях (которые захватываются сокращений Кука), предполагая , что мы имеем алгоритм для решения , мы можем решить ¯ S A T просто запустив алгоритм S A T и возвращает обратное.$\mathsf{SAT}$$\overline{\mathsf{SAT}}$$\mathsf{SAT}$

Мой вопрос: почему мы должны использовать редукции Карпа для теории -полноты? Какое интуитивное понятие оно фиксирует? Как это связано с тем, как мы понимаем «сложность вычислений» в реальном мире?$\mathcal{NP}$

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

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

Теперь возникает вопрос: зачем нам это изучать (и любые другие виды сокращений, такие как таблица истинности, таблица слабой истинности и т. Д.)?

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

Другие типы сокращений определяются по аналогичным причинам. Если вам интересно, я бы посоветовал проверить «Классическую теорию рекурсии» Пьерджорджо Одифредди. У этого есть довольно всесторонняя глава о различных сокращениях и их отношениях.

Теперь для теории сложности аргумент похож. Если вы согласны с тем, что является чрезвычайно естественным классом проблем, и вы хотите изучать N P , то сокращения Кука слишком сильны. Естественный выбором является более слабым снижением таким образом, что N P замкнуто относительно него , и мы можем доказать существование полной задачи WRT к той редукции для N P . Сокращение Карпа - естественный выбор для этой цели.$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$

На этом сайте есть несколько вопросов, связанных с сокращениями Кука и Карпа. Я не видел четкого описания этого для неофита, потому что он во многом несколько тонок и является активной / открытой областью исследований. Вот некоторые ссылки, которые могут быть полезны для решения этой проблемы. Как резюмирует Википедия: «Сокращение« многие-один »является ценным, потому что большинство хорошо изученных классов сложности закрыты при некотором типе сводимости многие-один, включая P, NP, L, NL, co-NP, PSPACE, EXP и многие другие. Однако эти классы не закрыты при произвольных сокращениях «многие-один».

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

[1] Кук против Карпа-Левина: разделение понятий полноты, если NP не маленький (1992) Lutz, Mayordomo

[2] Кук и Карп всегда одинаковы? Бейгель и Фортноу

[3] Больше проблем с NP-Complete (PPT) см. На слайдах 9-14 об истории и различиях между Кука и Карпа.