Complexity Theory

Reducibility §

• A problem reduces to a problem if given any input to , we can construct an input such that is a yes instance of if and only if is a yes instance of . We denote to say that reduces to .
  • Intuition: This can be read as saying solving is at least as difficult as solving .

P and NP §

• The set consists of problems that are solvable in polynomial time.

  More formally ,if is the input size of an instance of the problem, there exists an algorithm whose runtime can be asymptotically upper bounded by a polynomial function in \

• The set is the set of decision problems which are solvable in non-deterministic polynomial time

  • Non Deterministic Polynomial Time means that we can guess the answer from polynomially many options in time

  • More formally, we can define this as follows.

    A certificate is defined as evidence (with polynomial size) that would lead us to establish whether a problem instance is a YES instance.

    A certifier is an algorithm that checks that the certificate is indeed a valid proof.

    A problem is in NP if there exists a certifier that can run in polynomial time.

• • Proof: A polynomial time certifier exists for a problem instance — the polynomial time algorithm itself that can be used to solve .

• Let .

  • If then because we can solve as follows: (1) polytime convert to , then solve .
  • If , then

• A decision problem is in NP-Hard if for every problem , .

• A decision problem is said to be NP-Complete if

  • For Every problem

• If a problem is NP-hard then it is at least as difficult to solve as NP.

• Any polynomial time algorithm for would give us proof that .

• A problem can be shown to be in NP-C by showing that

  • A problem exists such that .

Misc §

• PPAD is an interesting complexity class.

Links §

• P vs NP and the Computational Complexity Zoo
• Complexity: P, NP, NP-Completeness, Reductions