Gibt es Probleme, die selbst für Computer zu schwer sind? Ja. Wir werden in Aktivität 20 sehen, dass es einfach nicht möglich ist, mit einem ins Gespräch zu kommen - etwas, was Computer nicht können, nicht weil sie nicht sprechen können, sondern weil sie keine sinnvollen Dinge verstehen oder denken können. Aber das ist nicht die Art von ‚harten’ Problemen, über die wir hier sprechen - es ist nicht so, dass Computer keine Gespräche durchführen können, es ist eher so, dass wir selbst nicht wissen, wie es bei uns funktioniert und so können wir dem Computer nicht sagen, was zu tun ist. Aber in diesem Abschnitt gehen wir auf Probleme ein, bei denen es einfach ist, dem Computer zu sagen, was er tun soll - indem wir ein Programm schreiben - aber der Computer nicht tun kann, was wir wollen, weil es viel zu lange dauern wird: vielleicht Millionen von Jahren. Es reicht nicht, einen schnelleren Computer zu kaufen: Selbst wenn er hundert Mal schneller wäre, würde es immer noch Millionen von Jahre dauern; sogar eine Million mal schneller würde Hunderte von Jahre brauchen. Das nennt man ein hartes Problem - eines, das viel länger dauert, als die Lebensdauer des schnellsten Computers, der für eine Lösung gedacht ist!

Die Aktivitäten über Algorithmen haben mögliche Wege gezeigt, um Computerprogramme effizienter zu machen. In diesem Abschnitt befassen wir uns mit Probleme, für die es keine effizienten Lösungen gibt, also Probleme, für die Computer Millionen von Jahren für eine Lösung brauchen. Und wir werden auf das wohl größte Geheimnis der Informatik stoßen: dass niemand weiß, ob es einen effizienteren Weg zur Lösung dieser Probleme gibt! Es mag sein, dass noch niemand einen guten Weg gefunden hat, oder es kann sein, dass es gar keinen guten Weg gibt. Wir wissen es nicht. Und das ist nicht alles. Es gibt Tausende von Probleme, die, obwohl sie völlig anders aussehen, in dem Sinne äquivalent sind, dass, wenn eine effiziente Methode gefunden wird, um ein Problem zu lösen, sie in eine effiziente Methode umgewandelt werden kann, um alle Probleme zu lösen. In den folgenden Aktivitäten lernst du diese Probleme kennen.

Für Lehrpersonen

In diesem Abschnitt gibt es drei Aktivitäten. Die erste besteht darin, Karten zu färben und zu zählen, wie viele Farben benötigt werden, um benachbarte Länder voneinander zu unterscheiden. Die zweite erfordert die Fähigkeit, eine einfache Straßenkarte zu verwenden um Eiswagen an Straßenecken so zu platzieren, dass niemand zu weit gehen muss, um ein Eis zu bekommen. Die dritte ist eine Aktivität im Freien, wo mithilfe von Seil und Stöpseln untersucht wird, wie ein kurzes Netzwerk durch eine Reihe von Punkten erstellt werden kann.

Die Aktivitäten vermitteln einen praktischen Eindruck vom Begriff der Komplexität - wie Probleme, die sehr einfach zu erklären sind, sich als unglaublich schwierig herausstellen können. Diese Probleme sind nicht unverständlich. Es sind praktische Fragen, die in alltäglichen Aktivitäten wie Kartierung, Zeitplanung und Straßenbau entstehen. Die rechnerische Untermauerung stützt sich auf einen Begriff namens „NP-Vollständigkeit", der im Abschnitt „Worum geht es in dieser Aktivität?" am Ende jeder Aktivität erklärt wird. Obwohl die Aktivitäten selbst in beliebiger Reihenfolge angegangen werden können, sollen diese Abschnitte in der Reihenfolge gelesen werden, in der sie erscheinen. Wenn Sie das Ende erreicht haben, werden Sie die wichtigste offene Frage der modernen Informatik fest im Griff haben.

Die Fachbezeichnung für diesen Teil ist „hartnäckig", weil Probleme, die schwer zu lösen sind, als hartnäckig bezeichnet werden. Das Wort stammt aus dem lateinischen Wort ,tractare', das ,zu zeichnen' oder ,zu ziehen' bedeutet. Heute verstehen wir darunter, dass etwas ‚machbar’, d.h. leicht zu behandeln, biegsam oder fügsam ist. Hartnäckige Probleme sind solche, mit denen man nicht so leicht umgehen kann, weil es zu lange dauern würde, um eine Antwort zu finden. Auch wenn es vielleicht etwas esoterisch klingt, so ist doch die ‚Hartnäckigkeit’ von großem praktischen Interesse, denn ein Durchbruch in diesem Bereich würde für viele verschiedene Forschungsrichtungen große Auswirkungen haben. Zum Beispiel beruhen die meisten kryptografischen Codes auf der Hartnäckigkeit einiger Probleme und ein Krimineller, der es geschafft hat eine effiziente Lösung zu finden, könnte seinen großen Tag damit haben, Geheimnisse zu entschlüsseln und sie zu verkaufen, oder einfach gefälschte Banktransaktionen auszuführen. Wir werden diese Dinge in Kryptographie betrachten.