Showing NP, NP completeness or NP hardness

Question

Do I understand three categories correctly?

To show the problem X, NP:

• Show that X can be deterministically tested at polynomial time (Or X is solvable using NTM)

To show problem X, NP-Complete:

• Show that X can be deterministically tested at polynomial time (Or X is solvable using NTM)
• Show that for the well-known problem NP-C L, L ≤p X
• Show that for the well-known problem NP-C L, X ≤p L (is this step necessary? If so, does this distinguish a purely NP-Hard problem from the NP-C problem?)

To show problem X, NP-Hard:

• Show that for the well-known problem NP-C L, L ≤p X

Answer 1

You almost got it.

Given a problem X, to show that it is an NPC, you do not need to show an NPC X ≤p Lfor some problem L.

, , X NP ( 1), , L - NP-Complete. NP-Complete , NP L , X, (3) NPC .

---

, , :

X, NP:

• , X ( X NTM)

X, NP-Hard:

• , , NP-Hard L, L ≤p X

2. , L NP, L ≤p X ( , SAT NP-Hard).

X, NP-Complete:

• X - NP-Hard
• X NP