I language is NP-complete if it's NP-hard and also NP

• NP-completes languages are languages that are at least as hard as all NP problems, but they are still NP themselves.
• They can be considered the hardest problems of NP
• All problems in NP can be easily reduced to them

ALL NP-complete problems can be reduced to each other!

How to prove

Direct way (useless, theoretical bullshit)

• Steps:
  • Mathematically prove that all problems in NP can be reduced to it.
  • Mathematically prove that it's NP itself (by designing a NTM solver or a DTM verifier)
• Very difficult.
• Some scientists have done the math and proved certain problems are NP-complete in this way
  • SAT
  • 3SAT

Reduction

• Show that the language is NP (by designing a NTM solver or a DTM verifier)
• Show that an already known NP-complete problem can be reduced to it