[ad_1]
Das heutige Rätsel beleuchtet einen der größten Hits der theoretischen Informatik, ein verblüffendes Ergebnis, das selbst Experten auf diesem Gebiet verblüfft zurücklässt.
Zu diesem Ergebnis (dem PCP-Theorem) kommen wir später. Aber zuerst zur Herausforderung!
Es ist ein Worträtsel. Hinweise im Kreuzworträtselstil weisen jeweils auf eine vertikale Spalte hin. Die Antwort auf jeden Hinweis ist ein Wort mit drei Buchstaben, das aus den drei Buchstaben besteht, auf die der Hinweis hinweist.
Lassen Sie uns dieses Problem gemeinsam lösen. Ein Tier mit drei Buchstaben? Wie wäre es mit „Fledermaus“?
Jedes Mal, wenn wir eine überzeugende Antwort geben können, erhalten wir für jeden Buchstaben einen Punkt. „Bat“ gibt uns eine Punktzahl von 3.
Jetzt machen wir weiter. Hier ist eine Möglichkeit, das Raster zu vervollständigen.
Die roten Buchstaben sind diejenigen, die nicht in der Lösung enthalten sind.
Beachten Sie, dass dieses Raster keine vollständige Lösung darstellt. Die drei wichtigsten Hinweise sind vollständig beantwortet. Ich habe die grünen Pfeile des Hinweises „Verb“ hervorgehoben, die auf „bezahlen“ hinweisen. Aber die drei unteren Hinweise sind nur teilweise gelöst. Essen weist auf „pey“ hin, nicht auf „pea“. Wir können uns jedoch für jeden Buchstaben in einer potenziell richtigen Antwort einen Punkt geben, sodass wir für „pey“ 2 Punkte für die beiden richtigen Buchstaben in „pea“ erhalten. Gesamtpunktzahl: 15 Punkte.
So erhalten Sie eine vollständige Lösung mit einer maximalen Punktzahl von 18. Natürlich war „Katze“ ein viel offensichtlicherer Ausgangspunkt!
Der Sinn dieses Rätsels ist, sagt Dana Moshkovitz, Professorin für Informatik an der University of Texas in Austin, dass „es in Ordnung ist, eine Teillösung zu bekommen.“ Genau das macht den Spaß aus. Ziel ist es, die höchstmögliche Punktzahl zu erreichen.
Hier sind drei Beispiele, in aufsteigender Reihenfolge des Schwierigkeitsgrads.
Problem 1
Problem 2
In diesem Rätsel sind die Hinweise mehrdeutig: Einige Hinweise sind Synonyme für die Antwort, andere sind Beschreibungen der Antwort. „Ausruf“ bezieht sich also auf einen Ausruf.
Problem 3
Jetzt sind die Hinweise noch unklarer.
Ich bin um 17:00 Uhr in Großbritannien mit vollständigen Lösungen zurück. (Es gibt möglicherweise viele vollständige Lösungen.) In der Zwischenzeit KEINE SPOILER. Bitte besprechen Sie Ihre Lieblingswörter mit drei Buchstaben.
[If any enterprising reader wants to make an interactive version of this puzzle, please put the link below.]
Was haben diese Rätsel also mit einem der wichtigsten Ergebnisse der Informatik zu tun? Tragen Sie mit.
Vor fünfzig Jahren entdeckten Informatiker, dass viele natürlich auftretende Probleme, etwa wie man Koffer unterschiedlicher Größe am besten im Kofferraum eines Autos stapelt, nach der Vergrößerung so komplex werden, dass Computer sie nicht in angemessener Zeit lösen können. Überraschenderweise stellt sich auch heraus, dass es genauso schwierig ist, ungefähre Antworten auf diese Koffer-im-Koffer-Probleme zu finden.
Die Analogie zum heutigen Rätsel besteht darin, dass das Rätsel eine korrekte Lösung, aber auch „ungefähre“ Lösungen hat. Wie wir gesehen haben, können Sie sowohl die Gesamtpunktzahl als auch die Teilpunktzahl erhalten. Stellen Sie sich vor, Sie würden diese Art von Puzzle mit mehr Hinweisen, Buchstaben und Pfeilen vergrößern. Die Unterscheidung zwischen Rätseln, die eine perfekte Lösung ergeben, und solchen, die eine Teillösung liefern, ist so komplex, dass Computer dies nicht in angemessener Zeit bewältigen können.
Dieses Fachgebiet – das Studium der „Näherungshärte“ – weist enge Verbindungen zum PCP-Theorem auf, ein erstaunliches Ergebnis, das mathematische Beweise betrifft. Wenn Sie einen mathematischen Beweis überprüfen möchten, müssen Sie ihn normalerweise Zeile für Zeile überprüfen, um festzustellen, ob er keine Fehler enthält. Zum Beispiel, wenn ein Lehrer Ihre Arbeitsabläufe durchgeht, um sicherzustellen, dass jede Schlussfolgerung ein logischer Schritt ist.
Das PCP-Theorem zeigt jedoch, dass Sie einen Beweis nicht Zeile für Zeile überprüfen müssen, um sicherzustellen, dass keine Fehler vorliegen. Stattdessen kann man den Beweis so umschreiben, dass man ihn überprüfen kann, indem man zufällig nur zwei oder drei Bits aus dem Beweis auswählt und nur diese Bits prüft, also an zwei oder drei Stellen prüft, ob das Bit entweder eine 0 oder eine 0 ist a 1. Nur ein paar Bits! Für jeden mathematischen Beweis!
Das obige Rätsel ist eine vereinfachte Version des PCP-Theorems, sagt Dana Moshkovitz, die es erfunden hat, um ihren Schülern das Thema näherzubringen. Sie fügt hinzu: „Praktisch *alle* bekannten Ergebnisse, die wir heute zur Härte der Approximation haben, beginnen mit dem PCP-Theorem in der Form eines Worträtsels.“
Ja, das ist etwas verwirrend, da es beim Worträtsel selbst nicht um die Überprüfung von Beweisen geht. Sie können den Link jedoch sehen, wenn Sie jedes Wort im Wesentlichen als „Überprüfung“ einer vollständigen Lösung betrachten.
Das PCP-Theorem (die Buchstaben stehen für probabilistisch überprüfbarer Beweis) war ein großer theoretischer Fortschritt, der wichtige praktische Anwendungen verspricht. So kann beispielsweise ein Computer mit kleinem Speicher sehr effizient überprüfen, ob ein großer Computer etwas richtig gemacht hat, wie beispielsweise ein iPhone, das die Integrität eines Programms in der Cloud überprüft. Diese Technologie wird bereits in Blockchains eingesetzt, beispielsweise vom israelischen Tech-Einhorn StarkWare.
Wenn Sie mehr über das PCP-Theorem erfahren möchten, finden Sie hier einen großartigen Artikel von Dana, der in XRDS, dem Studentenmagazin der Association for Computing Machinery, erschien.
Derzeit bin ich Wissenschaftskommunikator am Simons Institute for the Theory of Computing der University of California, Berkeley.
Seit 2015 stelle ich hier jeden zweiten Montag ein Rätsel. Ich bin immer auf der Suche nach tollen Rätseln. Wenn Sie einen vorschlagen möchten, senden Sie mir eine E-Mail.
[ad_2]
Source link