Докажите, что проблема NP-трудна, а не NP-завершена в не в P

Question

Если A не NP-жесткий, но не NP-полный, то докажите, что A не в P.

A NP-труден, если существует NP-полная задача B, такая что B сводится к A за полиномиальное время. A является NP-полной, если A находится в NP, и все NP-задачи сводятся к A за полиномиальное время. Но A не является NP-полным, поэтому одно или оба из этих условий должны быть ложными. Если A отсутствует в NP, то A нет в P. Другой случай состоит в том, что существует хотя бы одна NP-проблема, которая не сводится к A за полиномиальное время. Вот где я застрял. Как мне узнать, что существует NP-полная проблема, которая сводима, и NP-проблема, которая не сводима к A, отсутствует в P?

Answer 1

Если задача A является NP-сложной, то все NP-задачи сводятся к A за полиномиальное время.

Доказательство: Поскольку проблема A не является NP-полной, существует проблема B, как определено выше. Все задачи C в NP могут быть уменьшены до B за полиномиальное время, тогда B может быть уменьшено до A за полиномиальное время. Композиция алгоритмов полиномиального времени полиномиальна, поэтому C можно уменьшить до A за полиномиальное время.

-

Так как A NP-Hard, но не NP-Complete, A не должно быть в NP, поэтому A также не в P.