• P is a complexity class that represents the set of all decision problems that can be solved in polynomial time by a deterministic Turing machine.
• That is, given an instance of the problem, the answer yes or no can be decided in polynomial time.
• Since they can be solved in polynomial time, they can also be verified in polynomial time. Therefore P is a subset of NP.
• Example
  • Given a connected graph G, can its vertices be colored using two colors so that no edge is monochromatic?
  • Algorithm: start with an arbitrary vertex, color it red and all of its neighbors blue, and continue. Stop when you run out of vertices or you are forced to make an edge have both of its endpoints be the same color.

• NP is a complexity class that represents the set of all decision problems for which the CORRECT answers can be VERIFIED in polynomial time by a deterministic Turing machine
• This means that if someone gives us an instance of the problem and a certificate (sometimes called a witness) to the answer is yes, we can check that it is correct in polynomial time.
• Example
  • Integer factorization is in NP. This is the problem that given integers n and m, is there an integer f with 1 < f < m, such that f divides n (f is a small factor of n)?
  • This is a decision problem because the answers are yes or no. If someone hands us an instance of the problem (so they hand us integers n and m) and an integer f with 1 < f < m, and claims that f is a factor of n (the certificate), we can check the answer in polynomial time by performing the division n / f.

• Co-NP is a complexity class that represents the set of all decision problems for which the INCORRECT answers can be VERIFIED in polynomial time by a deterministic Turing machine
• may or may not be the same as NP

• NP-Complete is a complexity class that represents the set of all problems X in NP for which any other NP problem Y could be polynomial-time reducible to X.
• So, what makes NP-Complete so interesting is that if any one of the NP-Complete problems were to be solved quickly, then all NP problems could be solved quickly. This is why “P = NP?” is such a famous question.
• Example
  • 3-SAT. This is the problem wherein we are given conjunction (ANDs) of 3-clause disjunctions (ORs), statements of the form
    • (x₁₁ OR x₂₁ OR x₃₁) AND
    • (x₁₂ OR x₂₂ OR x₃₂) AND
    • … AND
    • (x_1n OR x_2n OR x_3n)
  • where each x_ij is a boolean variable or the negation of a variable from a finite predefined list (x₁, x₂, …, x_n).
  • It can be shown that every NP problem can be reduced to 3-SAT. The proof of this is technical and requires the use of the technical definition of NP (based on non-deterministic Turing machines). This is known as Cook’s theorem.

class of decision problems in NP that are neither P nor NP-Complete. Ladner’s theorem asserts that, if P ≠ NP, then NPI is not empty

The complexity class of optimization problems within NP that finds the best solution from all feasible solutions

• NP-Hard are problems that are at LEAST as hard as the NP-Complete
• The precise definition here is that a problem X is NP-hard if there is an NP-complete problem Y, such that Y is reducible to X in polynomial time.
• Note that all NP-Complete problems are also NP-hard
• However, not all NP-hard problems are NP (or even a decision problem), despite having NP as a prefix. That is the NP in NP-hard does not mean non-deterministic polynomial time. Yes, this is confusing, but its usage is entrenched and unlikely to change
• since any NP-complete problem can be reduced to any other NP-complete problem in polynomial time, all NP-complete problems can be reduced to any NP-hard problem in polynomial time. Then, if there is a solution to one NP-hard problem in polynomial time, there is a solution to all NP problems in polynomial time
• Example
  • The halting problem is an NP-hard problem. This is the problem that given a program P and input I, will it halt? This is a decision problem but it is not in NP. It is clear that any NP-complete problem can be reduced to this one. As another example, any NP-complete problem is NP-hard

• NP-Easy are problems that are at MOST as hard as the NP-Complete or NP?