thm. Satisfiability Reducibility. All problems can be reduced to boolean satisfiability problems.

  • Optimization problems: choose some , then ask “is there a solution ?, ?” => Then do a binary search on or

def. Computationally tractable problems. There exists a polynomial time algorithm for the solution. The set of all computationally tractable problems is denoted .

thm. Polynomial Reduction. Problem that is an element of can be reduced to problem problem which is also in , if there exists a function such that:

  1. takes polynomial time to complete
    1. can be a many-to-one function
  • This is denoted
  • Visually:
  • Implications of when
    • is at least as hard as .
    • P-time:
      • If is a P-time problem and
      • ! If the input size to which is is bounded by
      • Then is also a P-time problem
    • NP-hardness:
      • If is NP hard → is also NP-hard
  • & Techniques for reduction of
    • Process:
    1. If is a min/maximization problem, convert it to a decision problem
    2. If construction is needed, construct from to : domain
      1. ! The construction may not suppose you know the answer .
      2. If it’s a graph, it should apply to any graph
      3. If it’s a set, it should apply to any set
        • If there is something like “exists solution of size ” in , this will probability be present in as well
    3. Prove that if answer to in domain , that implies answer to in domain .
    4. Prove that if answer to in domain , that implies answer to in domain .
    5. Proven!

Complexity Classes

Complexity classes are an extension of the Chompsky Heirarchy.

  1. P (Polynomial Time)
  2. NP (Nondeterministic Polynomial Time) The certificate exists that can be verified in polynomial time. A non-deterministic Turing Machine can solve it in polynomial time because it has many paths.
  3. co-NP
  4. NP-complete: Problems where any NP problem can be reduced into in polynomial time.
    1. If there is any NP-complete problem that can be shown to be solved in polynomial time, then P=NP.
    2. thm. Cook-Levin Theorem. CNF-SAT is NP-complete.
    3. & To prove a decision problem is NP-complete
      1. Show i.e. certificate can be checked in poly-time
      2. Show where is known NPC problem by…
        1. from solution of , construct solution of
        2. show that is solution for if and only if is solution for (both ways needed to show that non-solutions are non-solutions)
    4. “Completeness” can apply to any complexity class. It means that it is the “hardest” problem in that class.
  5. NP-hard: Problems that are at least as hard as all NP (and NP-complete) problems
    1. Equivalently, Problems that are as hard or harder than all NP problems

List of Problems and Reductions

NP-Complete Problems

Karp’s 21 NP-complete problems - Wikiwand Category:NP-complete problems - Wikipedia (DevonThink) NP-complete Reductions