Theoretische Informatik - ganz praktisch

7Komplexitätstheorie

Wie wir im vorangegangenen Kapitel gesehen haben, können Probleme, die nicht einmal berechenbar bzw. entscheidbar sind, in der Praxis vernachlässigt werden, denn jeder Lösungsversuch für sie muss zwangsläufig scheitern.

Genauer gesagt gilt das nur, falls die Churchsche These korrekt ist. Das wird aber von den meisten Informatikern nicht ernsthaft angezweifelt. Es sei auch erwähnt, dass es alternative Systeme wie Analogrechner [Jac60] gibt, welche der Churchschen These nicht unterliegen. Diese „rechnen“ dafür nicht exakt und ihre Ergebnisse müssen anders interpretiert werden als wir das hier getan haben.

Doch wenn ein Problem ...