Все проблемы NP также NP-полны?

Question

Определение NP-полного:

Проблема является NP-полным, если

1. относится к классу NP
2. , все остальные проблемы в NP полиномиальнопреобразование в него

Итак, если все другие проблемы в NP преобразуются в проблему NP-полной, то не значит ли это, что все проблемы NP также NP-полны?Какой смысл классифицировать эти два, если они одинаковые?

Другими словами, если у нас есть проблема NP, то через (2) эта проблема может превратиться в задачу NP-полной.Следовательно, проблема NP теперь NP-завершена, а NP = NP-завершена.Оба класса эквивалентны.

Просто пытаюсь прояснить это для себя.

Answer 1

Все ли проблемы NP тоже NP-полные?

Только если P = NP.

Answer 2

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

Примером такой проблемы является изоморфизм графов .

Ваше предложение «если у нас есть проблема NP, то [...] эта проблема может превратиться в задачу NP-полной» неверно по следующей простой причине: любая проблема в P также есть в NP, но в P является NP-полным (если, конечно, P = NP).

Answer 3

По крайней мере, должно быть возможно показать, что ряд полных задач NP также есть в P. Возьмем, к примеру, проблему отделения нечетных простых чисел от составных нечетных чисел в наборе нечетных чисел.Можно получить метод в P, делающий это.Метод проверки также может быть в P, как обсуждено в ссылке ниже.

https://www.academia.edu/s/bcb7736e1e/proof-of-the-p-verses-np-problem-part-two?source=link

Возьмите проблему гипотезы Гольдбаха, Это может быть показано NP завершено, простые числа складываются вчетное число больше 2 может быть получено за линейное время.Каждое число Гольдбаха имеет свою собственную характеристическую линию с точками Гольдбаха в виде точек с простыми координатами, которые складываются в число Гольбаха.См. Ссылку ниже для получения дополнительной информации:

https://www.academia.edu/35904487/Proof_of_the_P_verses_NP_problem-part_one

Answer 4

Если задача A полиномиально преобразуется в проблему B, это не обязательно означает, что проблема B полиномиально преобразуется в проблему A. Проблема может быть сведена только к проблеме равной или большей сложности.

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