Ihre Beiträge sind uns willkommen! Schreiben Sie uns Ihre Fragen und Anregungen, Ihre Kritik oder Zustimmung. Wir veröffentlichen hier laufend Ihre aktuellen Zuschriften.
Die hier gebrachte Definition des Begriffs mathematischer Konstante ist nicht die Allgemeinste (allerdings die Definition, welche z.B. auch auf mathworks oder dem deutschsprachigen Wikipedia-Artikel verwendet wird). Die Bedingungen, dass die Zahl reell und nicht-ganzzahlig ist, wird häufig weggelassen.
Aus dem Argument in Klammern bzgl. der Nicht-Ganzzahligkeit von mathematischen Konstanten kann man - sofern man dem Argument bzw. Begründung zustimmt - entweder folgern, dass alle rationalen Zahlen (welche nicht-ganzzahlig sind) nun mathematische Konstanten wären, oder aber mit einem (zu dem Argument bzgl. der Nicht-Ganzzahligkeit) analogen Argument zu dem Schluss kommen, dass eben alle rationalen Zahlen keine Konstanten sein könnten.
Der (Haupt-)Grund für das Ausschließen von Ganzen Zahlen in der Definition einer mathematischen Konstante (sofern dieses gemacht wird) ist eigentlich, dass man jeweils einfache Darstellungen der jeweiligen Zahlen (z.B. im Dezimalsystem) hat, so dass eine weitere Definition dieser Zahlen über eine Folge (oder (unendliche) Reihe) oder auf andere Art und Weise nicht nötig ist (und zwar auch dann nicht, wenn eine solche Zahl nun der Grenzwert einer wichtigen Folge oder Wert einer wichtigen unendlichen Reihe wäre - man spricht dann eher (nachdem man den Grenzwert bzw. den Wert ermittelt hat) nur davon, dass die Folge nun den Grenzwert hätte oder die Reihe den Wert hätte).
Die Einschränkung darauf, dass eine mathematische Konstante bitteschön reell sein sollte, liegt u.a. daran, dass man bei komplexen Zahlen diese näturlich - im Prinzip - in einen rellen Anteil und einen imaginären Anteil zerlegen kann (wobei auch bei den sogenannten Quanterionen, welche nur ein Schiefkörper, aber kein Körper, sind, solche Zahlen in andere Anteile zerlegen kann).
Danke für das nette Problem. Ich habe mir ein kleines Pythonprogramm geschrieben, welches alle Möglichkeiten durchgeht und damit die Zahl 169 (in Basis 10) und die dazugehörige Basis 4 für die Umkehrzahl als Lösung mit kleinster Basis gefunden, denn 961_{4}=9*16+6*4+1=169_{10}.
Zusätzlich hier noch die Liste aller möglichen Lösungen:
169 in Basis 10 = 961 in Basis 4
196 in Basis 10 = 691 in Basis 5
236 in Basis 10 = 632 in Basis 6
395 in Basis 10 = 593 in Basis 8
834 in Basis 10 = 438 in Basis 14
371 in Basis 10 = 173 in Basis 16
912 in Basis 10 = 219 in Basis 21
961 in Basis 10 = 169 in Basis 28
Liebe Grüße
Ihr Artikel über Zero-Knowledge-Proofs (ZKP) stellt einige komplexe Sachverhalte aus der Berechenbarkeitstheorie anschaulich und verständlich dar. Ihre Beschreibung des Prinzips der ZKP, die ich selbst noch nicht kannte, fand ich einleuchtend und interessant zu lesen. Auch die Reduktion des 3SAT-Problems auf das Graphfärbungsproblem, welche eine klassische und sehr schöne Konstruktion auf diesem Gebiet darstellt, haben Sie anschaulich erklärt - und dabei gezeigt, dass Mathematik auch bunt und farbenfroh sein kann.
Allerdings ist Ihr Artikel durchzogen von einem fehlerhaften Leitmotiv über beweisbare mathematische Aussagen, und das Narrativ ist angetrieben von der Behauptung, jede solche Aussage ließe einen ZKP zu. Diese Behauptung ist leider völlig falsch. Sie entsteht, wie ich vermute, aus einer Verkettung einer größeren Zahl von Missverständnissen.
Das 3SAT-Problem ist die Aufgabe, für eine gegebene Konjunktive Normalform (CNF) mit dreistelligen Klauseln zu entscheiden, ob diese erfüllbar ist. Hier ist schon die erste Hürde: *Erfüllbarkeit* bedeutet, dass eine Belegung der vorkommenden propositionalen Variablen x_1, x_2, ... mit "wahr" und "falsch" *existiert*, sodass die Formel unter dieser Belegung zu "wahr" ausgewertet wird. "Beweisbarkeit" oder "Gültigkeit" einer Formel ist leider etwas anderes:
Eine Formel ist gültig, wenn sie *unter jeder möglichen Belegung* der Variablen zu "wahr" auswertet. Der Satz "Gibt es eine geeignete Kombination von »wahr« und »falsch« (beziehungsweise 1 und 0), dann ist die Aussage korrekt – und somit auch bewiesen (es liegt kein Widerspruch vor)." aus dem Artikel ist somit falsch. Leider werden die Begriffe Erfüllbarkeit und Beweisbarkeit hier nicht voneinander abgegrenzt und fälschlicherweise gleichgesetzt.
Anschließend wird das Erfüllbarkeitsproblem auf das Graphfärbungsproblem reduziert. Mit der vorhergehenden Beschreibung des ZKP für eine bestehende Färbung erhält man damit die Existenz eines ZKP für die Erfüllbarkeit jeder erfüllbaren CNF. Dank der NP-Vollständigkeit von 3SAT liefert das gleichzeitig auch die ZKP-Eigenschaft für jede Sprache in der Komplexitätsklasse NP. Das alleine ist schonmal eine bemerkenswerte Eigenschaft.
An dieser Stelle jedoch wird der Artikel sehr überenthusiastisch.
Zum Einen ist da das Problem Erfüllbarkeit vs Beweisbarkeit/Gültigkeit. Das Gültigkeitssproblem lässt sich tatsächlich mit dem Erfüllbarkeitsproblem in Beziehung bringen: Eine Formel in klassischer Aussagenlogik ist gültig genau dann, wenn ihre Verneinung *unerfüllbar* ist. Damit ist Gültigkeit also praktisch das Gegenteil des Erfüllbarkeitsproblems - beziehungsweise sein Komplement. Man sagt, Gültigkeit liegt in der Komplexitätsklasse CoNP der Probleme, deren Komplemente in NP liegen. Wir erhalten also keineswegs die ZKP-Eigenschaft für alle beweisbaren Aussagen - nur für die erfüllbaren.
Das Problem mit der Behauptung "Alle beweisbaren mathematischen Aussagen hätten einen ZKP" ist allerdings noch wesentlich größer. Es hängt an der folgenden Aussage über CNFs aus dem Artikel:
"Tatsächlich lässt sich jede mathematische Aussage in die folgende Form übertragen: (a1 ∨ b1 ∨ c1) ∧ (a2 ∨ b2 ∨ c2) ∧ … ∧ (an ∨ bn ∨ cn)".
Auch diese Aussage ist leider falsch.
Sie ist korrekt für Aussagen in klassischer Logik, welche lediglich aus Und-, Oder- und Nicht-Verknüpfungen von absoluten Atomaraussagen bestehen. Dieser Formalismus ist allerdings bei Weitem nicht ausreichend, um mathematische Aussagen in voller Allgemeinheit zu formulieren.
Denn um Mathematik in ihrer vollen Schönheit zu betreiben, braucht es die Möglichkeit, die Welt, die darin existierenden Objekte, und deren Relationen untereinander zu beschreiben. Dafür braucht man unter anderem formale Mittel, um Aussagen der Art "Für alle Objekte einer Art gilt..." oder "Es existieren Objekte, für die gilt..." zu formalisieren. Dies führt zur wesentlich mächtigeren Prädikatenlogik (erster Stufe), in deren Kern Variablen stellvertretend für Objekte stehen, und die atomaren Aussagen Prädikate sind, welche Variablen gewisse Eigenschaften attestieren. Darüberhinaus gibt es die Quantoren ∀ (für alle) und ∃ (es existiert), welche diese Variablen binden. Diese Prädikatenlogik bildet tatsächlich den Rahmen, in dem (fast) die gesamte moderne Mathematik gewebt wird.
Prädikatenlogische Aussagen lassen sich allerdings im Allgemeinen *nicht* auf die im Artikel beschriebenen CNFs reduzieren. Tatsächlich wäre das fatal und im Widerspruch zu der zentralen Erkenntnis, dass die Prädikatenlogik unentscheidbar ist - kein Computer kann jemals für alle möglichen solchen Aussagen entscheiden, ob sie wahr oder falsch sind.
Leider untergräbt dies auch das Leitmotiv des ZKP für die Riemann'sche Vermutung, welches sich durch den Artikel zieht. Denn diese Vermutung ist natürlich eine Aussage in Prädikatenlogik erster Stufe:
∀z ∈ C.ζ(z) = 0 ⇒ z ∈ −2N ∨ Re(z) = 1/2.
Als solche kann sie nicht in eine Konjunktive Normalform in klassischer Logik überführt werden, und ein ZKP lässt sich (mit den Argumenten des Artikels) nicht finden.
Ich möchte mich an dieser Stelle dafür entschuldigen, dem Artikel ein wenig das Rückgrat gebrochen zu haben. Gerade die theoretische Informatik wird gerne als sehr trocken und abstrakt wahrgenommen, und daher möchte ich Ihnen dafür danken, dass Sie sich die Mühe machen, diese Themen für ein breiteres Publikum aufzuarbeiten.
Die Rätselfrage hätte vielleicht lauten können, ob das Spiel fair ist? Bei Einsatz von 1€ ist der erwartete Gewinn abzgl. Einsatz: 2/21*9€-1€=-1/7€<0. Das Spiel ist also ein Verlustgeschäft für den Spieler.
Ein Zufallsspiel muss nicht notwendigerweise durch einen mathematischen Algorithmus (deterministisch) gesteuert werden. Das zeigen der Würfel, das Glücksrad oder das Roulett. Auch elektrische Vorgänge können praktisch nichtdeterministisch sein. In all diesen Fällen hat man grundsätzlich das Problem, dass das Zufallsexperiment schwer oder gar nicht auf seine Eigenschaften hin untersucht werden kann oder sich diese im Laufe der Zeit ändern (Verschleiß, Alterung). Auch mathematische Generatoren von Pseudozufallszahlen können schwere Fehler aufweisen (Forsythe, Malcolm, Moler: Computer Methods for Mathematical Computations, 1977).
Das geht einfacher und schneller:
- 8 Unbekannte und 7 Gleichungen d.h. eine Unbekannte kann als freier Parameter verwendet werden
- Setze also y = 1 und folge den weiteren Gleichungen
- Endet dann bei x = 24 und somit x * y = 24
arbeite den Kreis gegen den Uhrzeigersinn ab beginnend mit
fx=6, erweitern mit e ergibt links ef, was nach nächster Gleichung 3 ist,d.h.
3x=6e, erweitern mit d ergibt rechts de, was nach nächster Gleichung 4 ist, d.h.
3dx=24, erweitern mit c ...
6x=24c, erweitern mit b ...
6bx=24*3, erweitern a ...
6x=24*3a, erweitern mit y ...
6xy=24*3*2, ergo
xy=24
Auch ich kann mit dem Rätsel nicht viel anfangen, denn meiner Meinung nach sind zwei Schritte notwendig:
1) Finden einer passenden Folge - da habe ich keine Ahnung, wie mand das außer durch Raten und Probieren bewerkstelligen soll (da fehlt es mir an einer wohlüberlegten Vermutung), auch Schummeln half nicht (selbst bei den in der
On-Line Encyclopedia of Integer Sequences® (OEIS®) zur Verfügung stehenden Folgen konnte ich weder für die angegebenen Folge noch für eine mit den deren Quadratwurzeln etwas annähernd ähnliches finden - vielen Dank an Manon Bischoff - nicht nur - für den Artikel Auf der Suche nach der langweiligsten Zahl der Welt!)
2) Beweis, dass es keine andere Folge gibt, die an einer anderen Stelle eine Abweichung hat (denn es wurde nur nach der Stelle und nicht nach der Folge gefragt).
Aber ich freue mich, dass verschiedene Arten von Rätseln gezeigt werden, da kann dann gern etwas dabei sein, womit ich nichts anfangen kann. Vielen Dank!
ZKP(Beweis ohne Information) baut sich auf Operation der Logik.
Die binäre Logik untersucht eine Aussage in Bezug auf die Operationen der binären Logik, ohne es zu wissen, ob die Aussage entweder wahr oder falsch ist. Die Frage ist, ob es eine Aussage gebe, die ständig wahr ist.
Ist eine Aussage atomar, kann die binäre Logik den Inhalt der Aussage nicht bestimmen. Es bleibt weiterhin zwei Möglichkeiten (entweder wahr oder falsch). Dieser Fall entspricht dem Münzenwurf, der sich mit der Riemannschen Vermutung verbinden lässt.
Ist die Aussage nicht atomar, so wird der Inhalt durch die Elementen (atomare) der Aussage und die zu der Aussage gehörenden logischen Operationen bestimmt.
Sei eine Aussage=a oder nicht a. Diese Aussage wird immer wahr sein. Jede Aussage kann in diese Form umschrieben werden. Hier sagt damit die binäre Logik, dass alles (auch Beweis, der keinerlei Information überliefert) beweisbar ist. Aber das ist ein falscher Weg, den auch die Vertreter des ZKP begehen. Denn die Logik liefert lediglich nur die Möglichkeit, aber sie ist wohl kein Beweis, sondern nur ein möglicher Argument.
Die Riemannsche Vermutung basiert auf wahre mathematische Ergebnisse, damit ist die binäre Logik nicht fähig es zu beweisen, dass die Vermutung beweisbar ist.
Die binäre Logik hat ihre Stärke natürlich. In den Bereichen, wo eine Lösung zwei Ergebnisse (zum Beispiel digitale Sprache, Kriminologie, usw.) liefern kann. Anders formuliert: Fallen die Operationen der binären Logik mit der mathematischen Operationen zusammen, dann ist die Logik fähig die mathematische Aussage zu beweisen.
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.
Der Residuensatz und der erstaunlich einfache Umgang mit komplexen Polstellen wäre mal interessant.
Im Übrigen ist der o.a. Artikel sehr gut aber für Normalbürger wahrscheinlich schwer verständlich, da sie die Gruppenaxiome und Ringe etc.nicht kennen.. Als Werkstoffwissenschaftler sind für mich natürlich Symmetriegruppen interessant, wie die 32 Kristallklassen. Für jeden Bürger sind die Galoisgruppen und Körpererweiterungen in der modularen Arithmetik wichtig. Sie sind die Basis der modernen Kryptographie.
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.
Tippfehler in der Lösung
23.05.2023, KuchenBC = √((BC)2 – (CE)2)
Einfache Lösung
22.05.2023, Helmut Wiessmannxy = a⋅y ⋅ b⋅c/a⋅b ⋅ d⋅e/c⋅d ⋅ f⋅x/e⋅f = 2 ⋅ 3/1 ⋅ 4/2 ⋅ 6/3 = 2⋅3⋅2⋅2 = 24
Definition von "mathematischer Konstante" (bzw. "mathematical constant")
22.05.2023, Björn StuhrmannAus dem Argument in Klammern bzgl. der Nicht-Ganzzahligkeit von mathematischen Konstanten kann man - sofern man dem Argument bzw. Begründung zustimmt - entweder folgern, dass alle rationalen Zahlen (welche nicht-ganzzahlig sind) nun mathematische Konstanten wären, oder aber mit einem (zu dem Argument bzgl. der Nicht-Ganzzahligkeit) analogen Argument zu dem Schluss kommen, dass eben alle rationalen Zahlen keine Konstanten sein könnten.
Der (Haupt-)Grund für das Ausschließen von Ganzen Zahlen in der Definition einer mathematischen Konstante (sofern dieses gemacht wird) ist eigentlich, dass man jeweils einfache Darstellungen der jeweiligen Zahlen (z.B. im Dezimalsystem) hat, so dass eine weitere Definition dieser Zahlen über eine Folge (oder (unendliche) Reihe) oder auf andere Art und Weise nicht nötig ist (und zwar auch dann nicht, wenn eine solche Zahl nun der Grenzwert einer wichtigen Folge oder Wert einer wichtigen unendlichen Reihe wäre - man spricht dann eher (nachdem man den Grenzwert bzw. den Wert ermittelt hat) nur davon, dass die Folge nun den Grenzwert hätte oder die Reihe den Wert hätte).
Die Einschränkung darauf, dass eine mathematische Konstante bitteschön reell sein sollte, liegt u.a. daran, dass man bei komplexen Zahlen diese näturlich - im Prinzip - in einen rellen Anteil und einen imaginären Anteil zerlegen kann (wobei auch bei den sogenannten Quanterionen, welche nur ein Schiefkörper, aber kein Körper, sind, solche Zahlen in andere Anteile zerlegen kann).
Lösung mit kleinerer Basis
21.05.2023, Alexander ThallerZusätzlich hier noch die Liste aller möglichen Lösungen:
169 in Basis 10 = 961 in Basis 4
196 in Basis 10 = 691 in Basis 5
236 in Basis 10 = 632 in Basis 6
395 in Basis 10 = 593 in Basis 8
834 in Basis 10 = 438 in Basis 14
371 in Basis 10 = 173 in Basis 16
912 in Basis 10 = 219 in Basis 21
961 in Basis 10 = 169 in Basis 28
Liebe Grüße
Beweisbarkeit ist nicht Erfüllbarkeit, und mathematische Aussagen sind weit mehr als CNFs.
21.05.2023, Frederik HennigIhr Artikel über Zero-Knowledge-Proofs (ZKP) stellt einige komplexe Sachverhalte aus der Berechenbarkeitstheorie anschaulich und verständlich dar. Ihre Beschreibung des Prinzips der ZKP, die ich selbst noch nicht kannte, fand ich einleuchtend und interessant zu lesen. Auch die Reduktion des 3SAT-Problems auf das Graphfärbungsproblem, welche eine klassische und sehr schöne Konstruktion auf diesem Gebiet darstellt, haben Sie anschaulich erklärt - und dabei gezeigt, dass Mathematik auch bunt und farbenfroh sein kann.
Allerdings ist Ihr Artikel durchzogen von einem fehlerhaften Leitmotiv über beweisbare mathematische Aussagen, und das Narrativ ist angetrieben von der Behauptung, jede solche Aussage ließe einen ZKP zu. Diese Behauptung ist leider völlig falsch. Sie entsteht, wie ich vermute, aus einer Verkettung einer größeren Zahl von Missverständnissen.
Das 3SAT-Problem ist die Aufgabe, für eine gegebene Konjunktive Normalform (CNF) mit dreistelligen Klauseln zu entscheiden, ob diese erfüllbar ist. Hier ist schon die erste Hürde: *Erfüllbarkeit* bedeutet, dass eine Belegung der vorkommenden propositionalen Variablen x_1, x_2, ... mit "wahr" und "falsch" *existiert*, sodass die Formel unter dieser Belegung zu "wahr" ausgewertet wird. "Beweisbarkeit" oder "Gültigkeit" einer Formel ist leider etwas anderes:
Eine Formel ist gültig, wenn sie *unter jeder möglichen Belegung* der Variablen zu "wahr" auswertet. Der Satz "Gibt es eine geeignete Kombination von »wahr« und »falsch« (beziehungsweise 1 und 0), dann ist die Aussage korrekt – und somit auch bewiesen (es liegt kein Widerspruch vor)." aus dem Artikel ist somit falsch. Leider werden die Begriffe Erfüllbarkeit und Beweisbarkeit hier nicht voneinander abgegrenzt und fälschlicherweise gleichgesetzt.
Anschließend wird das Erfüllbarkeitsproblem auf das Graphfärbungsproblem reduziert. Mit der vorhergehenden Beschreibung des ZKP für eine bestehende Färbung erhält man damit die Existenz eines ZKP für die Erfüllbarkeit jeder erfüllbaren CNF. Dank der NP-Vollständigkeit von 3SAT liefert das gleichzeitig auch die ZKP-Eigenschaft für jede Sprache in der Komplexitätsklasse NP. Das alleine ist schonmal eine bemerkenswerte Eigenschaft.
An dieser Stelle jedoch wird der Artikel sehr überenthusiastisch.
Zum Einen ist da das Problem Erfüllbarkeit vs Beweisbarkeit/Gültigkeit. Das Gültigkeitssproblem lässt sich tatsächlich mit dem Erfüllbarkeitsproblem in Beziehung bringen: Eine Formel in klassischer Aussagenlogik ist gültig genau dann, wenn ihre Verneinung *unerfüllbar* ist. Damit ist Gültigkeit also praktisch das Gegenteil des Erfüllbarkeitsproblems - beziehungsweise sein Komplement. Man sagt, Gültigkeit liegt in der Komplexitätsklasse CoNP der Probleme, deren Komplemente in NP liegen. Wir erhalten also keineswegs die ZKP-Eigenschaft für alle beweisbaren Aussagen - nur für die erfüllbaren.
Das Problem mit der Behauptung "Alle beweisbaren mathematischen Aussagen hätten einen ZKP" ist allerdings noch wesentlich größer. Es hängt an der folgenden Aussage über CNFs aus dem Artikel:
"Tatsächlich lässt sich jede mathematische Aussage in die folgende Form übertragen: (a1 ∨ b1 ∨ c1) ∧ (a2 ∨ b2 ∨ c2) ∧ … ∧ (an ∨ bn ∨ cn)".
Auch diese Aussage ist leider falsch.
Sie ist korrekt für Aussagen in klassischer Logik, welche lediglich aus Und-, Oder- und Nicht-Verknüpfungen von absoluten Atomaraussagen bestehen. Dieser Formalismus ist allerdings bei Weitem nicht ausreichend, um mathematische Aussagen in voller Allgemeinheit zu formulieren.
Denn um Mathematik in ihrer vollen Schönheit zu betreiben, braucht es die Möglichkeit, die Welt, die darin existierenden Objekte, und deren Relationen untereinander zu beschreiben. Dafür braucht man unter anderem formale Mittel, um Aussagen der Art "Für alle Objekte einer Art gilt..." oder "Es existieren Objekte, für die gilt..." zu formalisieren. Dies führt zur wesentlich mächtigeren Prädikatenlogik (erster Stufe), in deren Kern Variablen stellvertretend für Objekte stehen, und die atomaren Aussagen Prädikate sind, welche Variablen gewisse Eigenschaften attestieren. Darüberhinaus gibt es die Quantoren ∀ (für alle) und ∃ (es existiert), welche diese Variablen binden. Diese Prädikatenlogik bildet tatsächlich den Rahmen, in dem (fast) die gesamte moderne Mathematik gewebt wird.
Prädikatenlogische Aussagen lassen sich allerdings im Allgemeinen *nicht* auf die im Artikel beschriebenen CNFs reduzieren. Tatsächlich wäre das fatal und im Widerspruch zu der zentralen Erkenntnis, dass die Prädikatenlogik unentscheidbar ist - kein Computer kann jemals für alle möglichen solchen Aussagen entscheiden, ob sie wahr oder falsch sind.
Leider untergräbt dies auch das Leitmotiv des ZKP für die Riemann'sche Vermutung, welches sich durch den Artikel zieht. Denn diese Vermutung ist natürlich eine Aussage in Prädikatenlogik erster Stufe:
∀z ∈ C.ζ(z) = 0 ⇒ z ∈ −2N ∨ Re(z) = 1/2.
Als solche kann sie nicht in eine Konjunktive Normalform in klassischer Logik überführt werden, und ein ZKP lässt sich (mit den Argumenten des Artikels) nicht finden.
Ich möchte mich an dieser Stelle dafür entschuldigen, dem Artikel ein wenig das Rückgrat gebrochen zu haben. Gerade die theoretische Informatik wird gerne als sehr trocken und abstrakt wahrgenommen, und daher möchte ich Ihnen dafür danken, dass Sie sich die Mühe machen, diese Themen für ein breiteres Publikum aufzuarbeiten.
Mit freundlichen Grüßen,
Frederik Hennig
Wozu wird genannt, dass bei Gewinn der neunfache Einsatz ausgezahlt wird?
21.05.2023, KuchenEin Zufallsspiel muss nicht notwendigerweise durch einen mathematischen Algorithmus (deterministisch) gesteuert werden. Das zeigen der Würfel, das Glücksrad oder das Roulett. Auch elektrische Vorgänge können praktisch nichtdeterministisch sein. In all diesen Fällen hat man grundsätzlich das Problem, dass das Zufallsexperiment schwer oder gar nicht auf seine Eigenschaften hin untersucht werden kann oder sich diese im Laufe der Zeit ändern (Verschleiß, Alterung). Auch mathematische Generatoren von Pseudozufallszahlen können schwere Fehler aufweisen (Forsythe, Malcolm, Moler: Computer Methods for Mathematical Computations, 1977).
Wie groß ist der Wert?
21.05.2023, Kristof Alt- 8 Unbekannte und 7 Gleichungen d.h. eine Unbekannte kann als freier Parameter verwendet werden
- Setze also y = 1 und folge den weiteren Gleichungen
- Endet dann bei x = 24 und somit x * y = 24
kurze Lösung
21.05.2023, Kuchenfx=6, erweitern mit e ergibt links ef, was nach nächster Gleichung 3 ist,d.h.
3x=6e, erweitern mit d ergibt rechts de, was nach nächster Gleichung 4 ist, d.h.
3dx=24, erweitern mit c ...
6x=24c, erweitern mit b ...
6bx=24*3, erweitern a ...
6x=24*3a, erweitern mit y ...
6xy=24*3*2, ergo
xy=24
educated guess
20.05.2023, Andreas Schmidt1) Finden einer passenden Folge - da habe ich keine Ahnung, wie mand das außer durch Raten und Probieren bewerkstelligen soll (da fehlt es mir an einer wohlüberlegten Vermutung), auch Schummeln half nicht (selbst bei den in der
On-Line Encyclopedia of Integer Sequences® (OEIS®) zur Verfügung stehenden Folgen konnte ich weder für die angegebenen Folge noch für eine mit den deren Quadratwurzeln etwas annähernd ähnliches finden - vielen Dank an Manon Bischoff - nicht nur - für den Artikel Auf der Suche nach der langweiligsten Zahl der Welt!)
2) Beweis, dass es keine andere Folge gibt, die an einer anderen Stelle eine Abweichung hat (denn es wurde nur nach der Stelle und nicht nach der Folge gefragt).
Aber ich freue mich, dass verschiedene Arten von Rätseln gezeigt werden, da kann dann gern etwas dabei sein, womit ich nichts anfangen kann. Vielen Dank!
Die Riemannsche Vermutuung
20.05.2023, Otto MarkusDie binäre Logik untersucht eine Aussage in Bezug auf die Operationen der binären Logik, ohne es zu wissen, ob die Aussage entweder wahr oder falsch ist. Die Frage ist, ob es eine Aussage gebe, die ständig wahr ist.
Ist eine Aussage atomar, kann die binäre Logik den Inhalt der Aussage nicht bestimmen. Es bleibt weiterhin zwei Möglichkeiten (entweder wahr oder falsch). Dieser Fall entspricht dem Münzenwurf, der sich mit der Riemannschen Vermutung verbinden lässt.
Ist die Aussage nicht atomar, so wird der Inhalt durch die Elementen (atomare) der Aussage und die zu der Aussage gehörenden logischen Operationen bestimmt.
Sei eine Aussage=a oder nicht a. Diese Aussage wird immer wahr sein. Jede Aussage kann in diese Form umschrieben werden. Hier sagt damit die binäre Logik, dass alles (auch Beweis, der keinerlei Information überliefert) beweisbar ist. Aber das ist ein falscher Weg, den auch die Vertreter des ZKP begehen. Denn die Logik liefert lediglich nur die Möglichkeit, aber sie ist wohl kein Beweis, sondern nur ein möglicher Argument.
Die Riemannsche Vermutung basiert auf wahre mathematische Ergebnisse, damit ist die binäre Logik nicht fähig es zu beweisen, dass die Vermutung beweisbar ist.
Die binäre Logik hat ihre Stärke natürlich. In den Bereichen, wo eine Lösung zwei Ergebnisse (zum Beispiel digitale Sprache, Kriminologie, usw.) liefern kann. Anders formuliert: Fallen die Operationen der binären Logik mit der mathematischen Operationen zusammen, dann ist die Logik fähig die mathematische Aussage zu beweisen.
Die Logik verwirren mit drei Farben.
20.05.2023, Otto MarkusDie 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.
Mein Lieblingsthema für die nächste Publikation
20.05.2023, GeorgIm Übrigen ist der o.a. Artikel sehr gut aber für Normalbürger wahrscheinlich schwer verständlich, da sie die Gruppenaxiome und Ringe etc.nicht kennen.. Als Werkstoffwissenschaftler sind für mich natürlich Symmetriegruppen interessant, wie die 32 Kristallklassen. Für jeden Bürger sind die Galoisgruppen und Körpererweiterungen in der modularen Arithmetik wichtig. Sie sind die Basis der modernen Kryptographie.
Anmerkungen
20.05.2023, Björn Stuhrmannjedes 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).
Verschiedene Fragestellungen
20.05.2023, Andreas Schmidt* 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.
Die Logik verwirren mit drei Farben.
20.05.2023, Otto MarkusDie 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.