Problem Solutions in Deterministic and Non-Deterministic Polynomial Time

CPa = DPa = Answer(Qa) for (Single Qa) in (Time = DP)

P = DP = Set of all DPa

NPa = NDPa = Answer(Qa) for (Single Qa) in (Time <= NDP)

NP = NDP = Set of all NDPa

(NP Hard)a=NPHa=NDPHa=Reduction(Qn) for (All Qn in NDP) in (Time = DP)

Note that (Time = DP) is a constraint for Reduction(Qn). There is no constraint for Time or Viability for Answer(Qn).


NP-complete =