Почему важно доказать, что проблема является NP-полной?

Правильно ли я понимаю, что доказательство того, что задача NP завершена, является успехом исследования? Если так, то почему?

Али, хороший вопрос.

Предположим, вы хотите показать, что некоторая проблема P является вычислительно сложной. Теперь вы можете предположить, что P сложно, просто основываясь на том факте, что у нас пока нет эффективных алгоритмов для него. Но это довольно неубедительные доказательства, нет? Вполне возможно, что мы упустили какой-то хороший способ взглянуть на P, который очень легко решить. Итак, чтобы предположить, что P сложно, мы бы хотели собрать больше доказательств. Сокращения предоставляют инструмент, чтобы сделать именно это! Если мы сможем свести какую-то другую естественную проблему Q к P, то мы показали, что P, по крайней мере, так же сложно, как Q. Но Q может быть проблемой из какой-то совершенно другой области математики, и люди могли десятилетиями бороться за решение Q также , Таким образом, мы можем рассматривать нашу неспособность найти эффективный алгоритм для Q как доказательство того, что P сложен. Если у нас много таких Q '

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

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

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

Давайте посмотрим , два разных случая , почему два разных человек хотел бы оказаться проблемой :$NP-complete$

$NP-complete$у вас есть некоторые доказательства этой вашей гипотезы, и вы должны начать рассматривать альтернативный подход (например, изменить проблему, чтобы она стала легче).

$NP-complete$ , вы получите некоторое представление:

$NP-complete$

$P=NP$$3-SAT$ .

$NP-complete$$CLIQUE$ проблемой )

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

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

Поэтому классификация одной проблемы как NPC обычно дает нам понимание других проблем, а также классов сложности.

Например, возьмем проблему изоморфизма графов (GI). В следующей статье:

Уве Шенинг, Изоморфизм графов находится в нижней иерархии , Труды 4-го ежегодного симпозиума по теоретическим аспектам информатики , 1987, 114–124; также: Журнал компьютерных и системных наук, вып. 37 (1988), 312–323.

доказано, что если GI ∈ NPC, то полиномиальная иерархия (PH) разрушается до своего второго уровня; который станет крупным прорывом в теории структурной сложности.

Я вижу, что предыдущие ответы объясняют, почему важно знать, является ли проблема NP-полной или нет, но ни один из них, по-видимому, не имеет прямого отношения к вопросу: «Доказательство»$p$NP-полная " не считается успехом исследования для всех$p$, Это зависит от различных вещей, таких как$p$ Интересно, есть ли в доказательстве новые методики,$p$ NP-полная "имеет интересные последствия и т. д.