algorithms-ch8: P, NP, NP-Hard and NP-Complete

概念

• Search Problem(eg:SAT)
  search problem can be verified in polynomial time is NP (all search problem is NP); search problem can be solved in polynomial time is P

• Search problem is NP-complete: if all other search problems reduce to it.

• Decision Problem
  A decision problem is a problem whose answer is YES or NO

• P (Polynomial time)
  The class P is the set of all decision problems that can be solved in polynomial time in the size of their encoding (ie. polynomial number of operations)

• NP (Nondeterministic Polynomial time)
  The set of all decision problem such that if the answer is YES then there is a certificate of validity that can be checked in polynomial time in the size of their input (a yes answer for a decision problem can be verified in polynomial time)

• co-NP
  The set of all decision problem such that if the answer is NO then there is a certificate of validity that can be checked in polynomial time in the size of their input (a no answer for a decision problem can be verified in polynomial time)

定理各种

• Theorem1: P is a subset of NP. Also, P is a subset of co-NP
  (But it is not known if P=NP or if NP=co-NP)

• Polynomial time reducibility
  A decision problem P1 is polynomially reducible to a decision problem P2 (if given any instance of P1 we can convert it to an instance of P2 in polynomial time), so that P1 is true if and only if P2 is true.
  We write P1=<P2, which means that P1 is at least as hard as P2.

• NP-Completeness(CNF-SAT, cli)
  A decision problem P is NP-Complete if two conditions are satisfies:(1) It is NP; (2) Every other problem P' in NP is polynomially reducible to P.