Skip to the content ForoHackers
Log inJoin

Complexity theory: start here

Complexity theory
#893 · Ophuscado · · Report

Complexity theory classifies problems, not programs, by the resources any algorithm needs to solve them: time, memory, randomness, communication. It explains why some problems have fast solutions and others seem to resist every attempt, and it underlies the security of modern cryptography.

Key concepts

  • Decision problems and classes: P is solvable in polynomial time, NP is checkable in polynomial time, PSPACE needs only polynomial memory.
  • Reductions: if problem A can be turned into problem B cheaply, then B is at least as hard as A.
  • NP-completeness: the hardest problems in NP; a fast algorithm for one would give one for all.
  • Hierarchy theorems: with more time or space you can provably solve more problems.
  • Beyond worst case: approximation, randomised algorithms, average-case hardness and parameterised complexity.

Vocabulary

  • Polynomial time: running time bounded by a power of the input size, the usual meaning of "efficient".
  • Certificate: a short proof that a yes answer is correct, which can be checked quickly.
  • Oracle: an imaginary black box that answers one question instantly, used to compare classes.
  • P versus NP: the open question of whether every quickly checkable problem is quickly solvable.

What to study, in order

  1. Big-O and the Turing machine as a model of cost.
  2. Write a brute-force solver and a verifier for a problem such as subset sum; compare their growth.
  3. Learn polynomial reductions and prove a small one by hand, such as from 3-SAT to clique.
  4. Read the Cook-Levin theorem and see why SAT is the first NP-complete problem.
  5. Survey space classes, randomised classes and approximation, and match real tasks to a class.

Related tags

#algorithms #computability #cryptography #formal-methods

Log in or join to reply.