Skip to the content ForoHackers
Log inJoin

Complexity theory: start here

Complexity theory
#3399 · · Quote · 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

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply