Пожалуйста, объясните, как правильна логика определения новой проблемы как NP-Complete.

Question

Используемая логика выглядит следующим образом - у нас есть существующий класс задач, NP-Complete.Теперь появляется новая проблема «Q».

Шаг 1 - Докажем, что Q в NP, хорошо и хорошо.

Шаг 2 - Покажем, что проблема в NP-C (скажем,O) сводится к Q. (O -> Q)

Теперь мы говорим, что, поскольку O является NP-сложным, и поскольку оно сводимо к Q, Q также должно быть NP-сложным, поскольку не существует более простогорешение для O, и если бы Q было более простым решением, тогда мы могли бы просто уменьшить O -> Q и решить Q.

Однако мы еще точно не знаем, что P! = NP.Возможно, эта новая проблема Q была проблемой, которая могла быть решена за полиномиальное время, и что для решения каждой из проблем в NPC нам нужно только преобразовать их в Q, а затем Q нужно решить.Если да, то как шаг 2 является достоверным доказательством того, что Q является NP-Hard?

Answer 1

NP-hard - это определение, включающее определенные классы сложности, а именно NP и NP-complete.Определения не относятся к классу сложности P.Сокращение времени по времени не относится к P.Подумайте об использовании словаря, из которого было удалено понятие P.

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