- El teorema de Church‑Turing nos dice qué puede ser calculado por cualquier algoritmo efectivo.
- La barrera de Razborov nos dice qué no podemos demostrar con los métodos de prueba más comunes (las “pruebas naturales”), suponiendo la existencia de generadores pseudorandom.