We start with a gentle introduction to the field.

Complexity questions in TCS are always tied to some problem. Classically, we study decision problems ↗ which are the problems where we are given an input and the goal is to produce a YES or NO answer. A complexity of such a problem is given by a “best” possible algorithm that solves it and is expressed in Big O notation ↗ in terms of ’n’ (size of the input). Of course, this algorithm is usually unknown to us. On one hand, we aim to design best algorithms that solve the problem. On the other hand, we may be able to show that algorithms that run so-and-so fast are impossible; this is tied to the notion of “hardness”.

Based on what we are able to show about the complexity of a problem we may be able to place it within some complexity class. For example, algorithms that run in polynomial time in n where n is size of the input are placed in class P. Definitions of complexity classes can be found on Complexity ZOO ↗.

It is common that the complexity classes form an onion-like structure or possibly overlap. One big part of the field is showing relation of these classes, e.g. whether one is inside another, or that two classes do not overlap. Some of these questions are very impactful on the whole field. On of these problems, called P versus NP ↗ was even declared a Millennium Prize Problem. As we were unable to resolve these for decades it became common practice to assume some result to derive other results, this gives us “conditional lower bounds”. Such a result would look like: Assuming that P is not equal to NP, we conclude that Vertex Cover problem cannot be solved in polynomial time.

Classes definitions

deterministic

  • P: Solvable in polynomial time by a deterministic machine.
  • NP: A solution can be verified in polynomial time by a deterministic machine.
  • coNP: A “no” instance can be verified in polynomial time by a deterministic machine.
  • NP-hard: Every problem in NP can be reduced in polynomial time to these problems.
  • NP-complete: Intersection of NP-hard and in NP.

parameterized

  • FPT: Fixed-Parameter Tractable problems, which can be solved by an algorithm whose running time is polynomial in the input size and any-computable in a parameter k.
  • W[1]: The first level of the W-hierarchy, which contains problems that can be reduced to the k-Clique problem.
  • W[t]: The t-th level of the W-hierarchy, which contains problems that can be reduced to the Weighted t-Clique problem.
  • XP: Slice-wise Polynomial problems, which can be solved by an algorithm whose running time is polynomial in the input size for every fixed value of the parameter k.

randomized

  • RP: A randomized algorithm can solve “yes” instances in polynomial time with a probability of error less than 1/2.
  • coRP: A randomized algorithm can solve “no” instances in polynomial time with a probability of error less than 1/2.
  • BPP: A randomized algorithm can solve both “yes” and “no” instances in polynomial time with a probability of error less than 1/3.
  • ZPP: A randomized algorithm can solve both “yes” and “no” instances in expected polynomial time.

Standard techniques

Books