NP-Completeness

NP is a class of decision problems

To prove a problem B is NP-complete, we need to prove

  1. BNP
  2. There is an NP-complete problem A such that ApB