Kommentare - - Seite 17

1. Micali, Goldreich und Wigderson haben "nur" gezeigt, dass
jedes Problem in NP einen Zero-Knowledge-Proof hat (wobei
ich hier die weitere Bedingung/Annahme, dass es Einwegfunktionen gibt bzw. eine etwas stärkere Bedingung,
Mal unter den Tisch fallen lasse). Natürlich kann man überlegen,
dass es eben auch für größere Problemklassen (wie NPSPACE)
auf ähnliche Art und Weise nun einen Zero-Knowledge-Proof erstellen könnte (allerdings dann mit "längerer" Laufzeit, also
z.B. nicht mehr (erwartbarer) "polynomieller" Laufzeit bzgl. der "Problemgröße").

2. Zum SAT-Problem: Das SAT-Problem (genauso wie 3-SAT) ist NP-vollständig, d.h. jedes Entscheidungsproblem in der Klasse NP läßt sich als SAT-Problem (bzw. auch 3-SAT-Problem bei dem jede Klausel 3 Variablen hat) formulieren (bzw. mittels "polynomieller" Reduktion darauf reduzieren). Andere mathematische Aussagen lassen sich zwar durchaus auch als SAT-Problem definieren, aber dann kann dabei die Eingabelänge des Problems doch stark wachsen (und zwar nicht nur "polynomiell" sondern auch exponentiell oder mehr).
Für das sogenannte QBF-Problem (Quantifizierte Boolsche Formeln; quantified Boolean formula) steht vor der boolschen Formel nun eine Reihe von Quantoren, bei denen sich die Quantoren forall und exists abwechseln, mit denen boolsche Variablen in der Formel "gebunden" werden. Bei einer Transformation von QBF-Problemen in SAT-Problemen würde nun die Eingabelänge (Länge der boolschen Formel) nun exponentiell wachsen. Andererseits ist QBF allerdings nur NPSPACE-vollständig (wobei NPSPACE=PSPACE gilt) und eben das QBF-Problem - wenn ich es richtig in Erinnerung habe - dafür genutzt wurde zu zeigen, dass jedes (Entscheidungs-)Problem in NPSPACE nun auf ein QBF-Problem reduziert werden kann (wieder mittels polynomieller Reduktion).

3. Bzgl. dessen, dass jede beweisbare mathematische Aussage als SAT-Problem definiert werden kann: Zuerst habe ich dazu tendiert, dass die Aussage falsch ist, aber dann, nach ein paar Überlegungen, bin ich zum Schluss gekommen, dass die Aussage (im Prinzip)¹ richtig ist.

Es ist allerdings so, dass man nicht - direkt - jede beliebige Aussage in einer Logik (wobei zu diesen Logiken auch CTL (Computational Tree Logic), LTL (linear temporal logic), modal Logiken etc. gehören) nun in einen boolschen Ausdruck (mit nur boolschen Variablen) transformieren kann (ohne dass dabei eben der boolsche Ausdruck "unendlich" lang werden würde), man muss dabei nämlich nur betrachten, dass in der Logik z.B. eine Variable nun mit dem "exists" Quantor gebunden sein könnte und der Definitionsbereich der Variablen nun z.B. die natürlichen Zahlen sein könnte (wie es sich beim "forall" Quantor verhält, überlasse ich dem Leser - nur als Hinweis: in der Mathematik überläßt man analoge Aussagen häufig dem Leser ;-) ).

Es ist allerdings so, dass jede Berechnung einer Turing-Maschine nun durch eine boolsche Formel ausgedrückt werden kann. Weiter ist es so, dass eben alle "Berechnungen" von Theorem-Provern (die es gibt) nun auch durch Turing-Maschinen erfolgen können (und bisher ist keine Klasse von Computern bekannt, welche im Hinblick auf Berechenbarkeit nun mächtiger als Turingmaschinen, sind - auch keine Quantencomputer). Weiter sind natürlich Aussagen nur "beweisbar" (bzw. sind als beweisbar anzusehen), wenn der Theorem-Prover (und damit eine zugehörige Turing-Maschine, welche die Berechnungen des Theorem-Provers simuliert) auch in endlicher Zeit zu einem Ergebnis kommt (womit auch eine geeignete - die Berechnungen simulierende - Turingmaschine auf der entsprechenden Eingabe in endlicher Zeit anhält), wobei allerdings jeder Berechnungsschritt der Turing-Maschine zu mindestens einer "Klausel" führt (wobei "Klausel" hier die Oder-verknüpften boolschen Variablen in Klammern bezeichnet).

Damit existiert also für jede beweisbare mathematische Aussage (vor allem, wenn man nur mathematische Aussagen mit wahr oder falsch als Ergebnis betrachtet) nun eine Darstellung als boolsche Formel (und damit als SAT-Problem), wobei allerdings diese boolsche Formel "sehr lang" werden kann, wie "schwierig" es nun ist zu einer mathematischen Aussage nun eine solche boolsche Formel zu finden, steht allerdings auf einem anderen Blatt.

Um allerdings die Transformation der mathematischen Aussage in eine SAT-Formel (endlicher Länge) hinzubekommen, muss man eben (a-priori) eine obere Schranke für die Anzahl der Rechenschritte kennen, im anderen Falle würde man - je nach Vorgehen - entweder eine SAT-Formel unendlicher Länge erhalten oder aber die SAT-Formel (bei zu kleiner Schätzung der Anzahl der Rechenschritte in der SAT-Formel) könnte man zu einem falschen Ergebnis gelangen (d.h. eine mathematische Aussage ist wahr, aber da die Turingmaschine nicht in einem akzeptierenden (Haltezustand) nach der angebenen Anzahl von Rechenschritten der SAT-Formel landen würde, würde man die Aussage für falsch halten).

Ansonsten könnte ich hier noch etwas zu Kolmogorov-Komplexität (bzw. Beschreibungskomplexität) von unterschiedlichen mathematischen Aussagen in der Formulierung als SAT-Problem schreiben und den Hinweis darauf, dass ein Problem, was in einer (unified) Beschreibungssprache (welche nicht SAT wäre) nun eine Länge von n hat, nun in SAT durchaus auch eine (minimale) Länge von exp(exp(n)) oder noch mehr haben könnte.

4. In Bezug zu "Wo ist Walter": Hier sollte nicht die gesamte Silhouette von Walter ausgeschnitten werden, da die Form der Silhouette von Walter von Wimmelbild zu Wimmelbild unterschiedlich sein kann, stattdessen sollte, damit eben möglichst wenig Informationen (und im besten Falle keine Informationen) bekannt werden, maximal der Kopf von Walter ausgeschnitten werden (wobei sofern der Kopf - abgesehen von Drehungen des gesamten Kopfes - auf unterschiedlichen Wimmelbildern eine unterschiedliche Form hat, dieses nicht ausreichend ist, damit durch das im Artikel beschriebene Verfahren keine Informationen bekannt werden). Denn die Form der Silhouette kann durchaus dabei helfen hinterher Walter zu finden. (Das Beispiel bzgl. der Spielkarten ist dagegen besser gewählt.)

ps. Sofern P=NP ist, könnte man überlegen, dass es keine Zero-Knowledge-Proofs für viele mathematischen Probleme gibt (aber dann sind die fast alle Informatiker/Mathematiker der Meinung, dass NP ungleich P ist, obwohl man bisher keinen Beweis für die Aussage hat - wobei der vielversprechenste Beweisversuch von Deolaliker war).

¹) Auf eine akademische Diskussion, ob nun eine (beweisbare) mathematische Aussage, dass eine (unendliche) Folge/Reihe den Grenzwert Pi hat, nun auch als (endliche) SAT-Formel ausgedrückt werden kann, verzichte ich hier (genauso auf die Diskussion bzgl. ähnlich gelagerter beweisbarer mathematischer Aussagen).

Es war interessant, den Artikel und die vielen Antworten (das ist wohl ein Highscore) zu lesen, aber ich denke auch, dass da unterschiedliche Fragestellungen mit unterschiedlichen richtigen Antworten vermischt werden, etwa
* Wie groß ist die Wahrscheinlichkeit, dass bei einem Wurf Kopf geworfen wird?
* Wie groß ist die Wahrscheinlichkeit, dass beim Aufwecken die Münze Kopf zeigt (weil am Sonntag Kopf geworfen wurde)?
Wenn dem so ist (was auch dadurch naheliegt, dass für beide Antworten - mehr oder weniger - gute Gründe genannt werden), wundere ich mich, warum darum so eifrig gestritten wird. Und ja, die Antwort Dornröschens hängt wohl auch davon ab, welches statistische Vorwissen sie hat.

Eine Aussage ist entweder wahr(grün) oder falsch(rot). Wo kommt die neutrale Aussage(blau) her?
Die Fachleute sollten mal am Ausgangspunkt der binären Logik bleiben und nicht so machen, als die binäre Logik drei Möglichkeiten hätte.
Eine Aussage A ist entweder wahr oder falsch. Werden n Aussagen mit dem Und verbunden, dann reicht eine falsche Aussage unter n aus, dass die zusammengesetzte Aussage falsch ist.
Werden N Aussagen mit Oder verbunden, dann reicht eine wahre Aussage aus, dass die zusammengesetzte Aussage wahr ist.
Nimmt man zu n eine neutrale hin, dann wird durch oder wahr sein.
Das nenne ich eine Pseudowissenschaft.
Ganz anders wäre das Problem, wenn man gleich am Anfang für eine Aussage drei Möglichkeiten annimmt.
Mit der neutralen kann das Und nichts anfangen. Aber das Oder ja, wenn die andere Aussage nicht neutral ist.
Hier aus folgt: eine beweisbare Aussage kann in drei Farben nicht umschrieben werden. Denn: Ist eine Aussage beweisbar, dann hat sie in sich keine elementare Aussage, die neutral ist.
Für die Wissenschaft ist "eine gefährliche Spiel", wenn man ohne Begründung zwei Möglichkeiten mit drei Möglichkeiten interpretiert.
Bemerkung: Ich kann gut verstehen, dass man alles erklären will. Aber, was man momentan nicht erklären kann, ist neutral.
Ein Beispiel, wie es gefährlich sein kann, wenn man mit den Und und Oder "herumspielt":
Angenommen man hat n Messwerte. nach den Messwerten wurde eine Formel angegeben.
A.) Sei ein Messwert falsch. Man verbindet die Werte mit Und, dann wird die Formel falsch. Mit dem Oder richtig.
B.) Sei ein Messwert richtig. Man verbindet die Werte mit Und, dann ist die Formel falsch. Mit dem Oder richtig.
Sicher, die Statistik funktioniert nicht nach diesem Gedanken, aber ich mag darauf hinweisen, dass man mit den Aussagen in Bezug auf die binären Operationen nicht alles erklären, beweisen, darstellen, usw. kann.

Guten Tag Frau Bischoff,
vielen Dank für Ihre immer wieder spannenden und gut verständlichen Beiträge aus der Welt der Mathematik! Lese ich immer gern.

Als Idee: interessant wäre vielleicht auch die Betrachtung eines Menschen aus topologischer Sicht. Wenn der Mund geschlossen ist, haben wir durch die beiden verbundenen Nasenlöcher im Wesentlichen einen Torus. Was passiert aber, wenn der Mund geöffnet wird? Ein Donut mit einem Loch im Torusring?
Oder wenn jemand Ohrringe trägt mit zwei Löchern in den Ohrläppchen, entfernt sich die Person damit von ihrem topologischen Ursprungszustand? :-)

Bei korrekt formulierter Spielregel (siehe oben) lautet das zentrale mathematische Argument am Beispiel, dass der Kandidat zunächst auf Tür 1 zeigt und der Moderator Tür 3 mit einer Ziege öffnet:

Die Wahrscheinlichkeit, dass der Moderator Tür 3 mit einer Ziege öffnet, beträgt 1/2, wenn das Auto hinter Tür 1 steht, aber 1, wenn es hinter Tür 2 steht.

Wir können in der Tat nur über die mathematischen Wahrscheinlichkeiten diskutieren. Und natürlich bedeutet eine Gewinnwahrscheinlichkeit von 2/3 keineswegs Sicherheit. Aber man kann Folgendes sagen: Wenn man das Spiel oft durchführt, ist etwa in 2/3 der Fälle der Gewinn zu erwarten. - Zum mathematischen Kern des Ziegenproblems werde ich gleich noch einen kurzen Kommentar schreiben.

Das Periodensystem der chemischen Elemente entstand vor ca. 150 Jahren.
Das Periodensystem der physikalischen Konstanten gibt es erst seit 5 Jahren.
Das Periodensystem von mathematischen Gruppen wird auch irgendwann gefunden werden. Die Periodensysteme der Chemie und der Physik bestehen aus Gruppen von Elementen bzw. von Konstanten mit jeweils ähnlichen Eigenschaften. Die Wissenschaftler wollen stets das "heuristische Prinzip" von Systemen mit Gruppen-Eigenschaften für weitere Entdeckungen nutzen.
Viele Grüße
Peter Pohling
www.naturkonstanten.de

Leider bin ich nicht "vom Fach", habe aber viele "erbauliche" Stunden zugebracht mit SAUTOY, Marcus du: "Die Mondscheinsucher. Mathematiker entschlüsseln das Geheimnis der Symmetrie, 2008, ISBN 978 3 406 57670 6 - finde leider trotz mehrfachen Suchens keinen Hinweis im Artikel zu dieser Lektüre - evtl. wäre auch ein Hinweis auf Symmetrien hilfreich, wie man sie in der Alhambra in Granada findet - hierzu war vor Jahren ein Artikel in SPEKTRUM.

Mit freundlichen Grüßen!

Ulrich Schmitz

Die falsche Methode funktioniert auch für alle Brüche, in denen Zähler und Nenner Vielfache von 11 sind, bspw 11/55=1/5 oder 22/66=2/6(=1/3). Soweit ich das hier lesen kann, bestand keine explizite Regel, nach der die zweistelligen Zahlen unterschiedliche Ziffern haben müssen (wobei natürlich klar ist, dass die Aufforderung in Zähler und Nenner einmal die erste und einmal die zweite Ziffer zu kürzen theoretisch auch so interpretiert werden könnte - so wie es geschrieben wurde verstehe ich die Einschränkung aber so, dass nur der Unterschied zwischen Einer- und Zehnerstelle explizit zu beachten war, nicht bestimmte Ziffern).

Da in der Aufgabenstellung nicht steht, dass A ungleich B gibt es neun weitere Lösungen.
11/11; 22/22; 33/33.........99/99

Die Rezension mit dem Titel 'Mathematik – kein einfaches Spiel' von Hartmut Weber hat mein Interesse an dem besprochenen Buch geweckt. Insbesondere möchte ich wissen, was der Buchautor meint, wenn Hartmut Weber über ihn schreibt: 'Folgerichtig widerspricht er scharf der Auffassung von Mathematik als Spiel, die sie vor allem als eine Wissenschaft sieht, in der ausgehend von Axiomen nach formalen Regeln (unabhängig von irgendeiner Realität) abstrakte logische Folgerungen gezogen werden. Dabei denkt er an Hilbert, wenn der in seinen »Grundlagen der Geometrie« den berühmt gewordenen Satz formuliert, nach dem »Punkte«, »Geraden« und »Ebenen« auch durch »Tische«, »Stühle« und »Bierseidel« ersetzt werden könnten.

"Folglich ist Sym(n−1) immer in der symmetrischen Gruppe Sym(n) enthalten – und zwar genau sechsmal (da man ja insgesamt n Murmeln einzeln festhalten kann)."
Müsste das "genau n Mal" heißen statt "genau sechsmal"? Käme mir plausibel vor, ohne mich weiter damit beschäftigt zu haben.
Viele Grüße
Gerhard Kraus

Rein mathematisch ist die Gewinnwahrscheinlichkeit 8/84.
Gewinnmöglichkeit: 8 Fälle.
Alle Möglichkeit: 84 Fälle ( Aus 9 Felder wähle ich 3 Felder aus).
BEMERKUNG:
Zufall ist Zufall, nach meiner Vorstellung, er hat keinen Prinzip. Zufall kann mathematisch nicht definiert werden.
Ein Spielautomat funktioniert grunds seinen Programms, also nach mathematischen Algorithmen. Der Zufall hat zwei Seiten. Eine wahrscheinliche und eine unbestimmbare. Die letztere kann mathematisch nicht bestimmt werden. Damit die Chance, dass ich gewinne, liegt zwischen 0 und 100 %.

Die zwei Diagonalen des Rechteckes schneiden sich im Origo des Kreises vom Zehneck. Das Rechteck wird durch die Diagonalen auf vier Dreieck zerteilt. Die Flächengröße sind gleich. Damit ist das Verhältnis 4/10. Es entspricht 40%.

Die Zahl von 9095 sichtbaren Sternen muss ich aber wohl halbieren, denn ich kann die unter dem Horizont ja nicht sehen ...??