Saltar al contenido ForoHackers

Complexity theory: start here

Teoría de la complejidad
#3399 · · Citar · Denunciar

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

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder