Type the two-step NP-completeness proof template

Answer

1. X in NP: give a certificate + poly-time verifier 2. X NP-hard: pick KNOWN-NPC Y, reduce Y <=p X - f is poly-time computable - y in Y <=> f(y) in X (both directions)

Step 1 is usually easy (describe what to check). Step 2 is the real work: the reduction goes FROM the known-hard problem INTO X, and you must prove the biconditional in both directions.