Wie sich zeigt, gibt es selbst unter denjenigen mathematischen Problemen, die ihrem Wesen nach algorithmisch sind, einige Klassen von Problemen, die wegen ihrer Eigenart um vieles schwieriger algorithmisch lösbar sind als andere. Die schwierigen lassen sich nur durch sehr langsame Algorithmen lösen (oder vielleicht mit Algorithmen, die unverhältnismäßig viel Speicherplatz erfordern, und so weiter). Mit derartigen Fragen befaßt sich die sogenannte Komplexitätstheorie.