Cílem přednášky je seznámit posluchače s oblastí výzkumu zvanou výpočetní složitost. K tomuto účelu popíšeme dva výsledky. První, tzv. PCP věta, říká zhruba, že je možno kódovat důkazy takovým způsobem, aby k ověřeni správnosti se stačilo podívat na několik náhodně vybraných bitů. Druhý výsledek říká, že pomocí kvantových počítačů (což je zatim jenom teoretický pojem) lze efektivně najít dělitele velkého složeného čísla. To se pomocí klasických počítačů neumí.