Avi Wigderson und der Einbruch des Zufalls in das Reich der Beweise

BLOG: Heidelberg Laureate Forum

Laureates of mathematics and computer science meet the next generation
Heidelberg Laureate Forum

Das erste Mal, dass mir der Name Avi Wigderson begegnete, war gleich ein feierlicher Anlass. Auf dem internationalen Mathematiker-Kongress in Zürich 1994 wurde ihm der Nevanlinna-Preis verliehen, eine Auszeichnung für Leistungen auf Weltniveau in der theoretischen Computerwissenschaft. Der Preis war nach dem Vorbild der Fields-Medaille in der Mathematik gebaut; insbesondere durfte der Preisträger am 1. Januar des Verleihungsjahres noch nicht 40 Jahre alt sein. Damals wurde unter anderem eine Erfindung Wigdersons ausgezeichnet, die als „zero-knowledge proof“ („Beweis mit null Ahnung“) bekannt geworden ist.

Inzwischen hat der junge Mann das gesetzte Alter von 65 erreicht – und den Abelpreis gewonnen. Der ist nach dem Vorbild des Nobelpreises konstruiert und wird typischerweise für ein wissenschaftliches Lebenswerk verliehen. Und in der Tat: Da ist in den letzten 27 Jahren noch allerlei dazugekommen. In seinem Vortrag auf dem letzten Heidelberg Laureate Forum bot Wigderson ein absolut überwältigendes Panorama der letzten Erkenntnisse aus der theoretischen Computerwissenschaft. Es ist aussichtslos, das hier auch nur ungefähr zu referieren. Aber ein paar Highlights will ich versuchen zu vermitteln. Für alle, die es genauer wissen wollen: Wigderson hat der Welt sein Buch „Mathematics and Computation“ geschenkt, in dem er diese neueren Entwicklungen umfassend beschreibt.

Was hat es mit dem Null-Ahnungs-Beweis auf sich? Ich (der „Beweiser“, „prover“) kann einem Gegenüber (dem „Prüfer“, „verifier“) etwas beweisen: eine mathematische Gleichung, ein ganzes Theorem oder auch nur die Tatsache, dass ich ein Geheimnis kenne. Und zwar so, dass der Prüfer von der Richtigkeit meiner Behauptung überzeugt ist, ohne von meinem Rechenweg, meiner Argumentation, meinem Geheimnis irgendetwas in Erfahrung gebracht zu haben! Ich könnte meiner Bank klarmachen, dass ich meine Geheimzahl kenne, ohne dass ich sie, wie heute üblich, in irgendein mir unbekanntes Gerät eintippen müsste. Das wäre durchaus hilfreich, denn damit müsste ich nicht mehr fürchten, dass jemand das Gerät manipuliert hat, so dass er die Geheimzahl mitlesen und sich hinterher gegenüber der Bank für mich ausgeben kann.

Aber wie soll das gehen? Im Prinzip so, dass der Prüfer dem Beweiser Fragen stellt, die dieser nur dann richtig beantworten kann, wenn er das Geheimnis kennt. Da die Computerwissenschaftler immer in Bits denken, soll es sich um Fragen handeln, auf die man nur mit 1 oder 0 („Ja“ oder „Nein“) antworten kann. Natürlich kann ein falscher Beweiser auf eine Frage irgendeine beliebige Antwort geben und damit, wenn er Glück hat, den Prüfer täuschen. Das gelingt ihm mit einer Wahrscheinlichkeit von 50 Prozent – bei der ersten Frage. Jede weitere Frage halbiert die Wahrscheinlichkeit des Gelingens, und nach der hundertsten richtig beantworteten Frage wird kein vernünftiger Prüfer mehr auf die Idee kommen, dass ein Betrüger am anderen Ende der Leitung sitzt. Man gewinnt also keine absolute Sicherheit, kommt aber der absoluten Sicherheit beliebig nahe. Und wem das nicht reicht, der hat die Freiheit, noch ein paar Fragen mehr zu stellen.

Aber das schwierigere Problem kommt erst noch: Welche Fragen darf der Prüfer überhaupt stellen? Die nur mit Kenntnis des Geheimnisses richtig zu beantworten sind, ihm selbst aber keine Information über das Geheimnis bringen? „Ist deine Geheimzahl gerade?“ scheidet jedenfalls aus; noch ein paar Fragen dieser Machart („Ist die erste Binärziffer deiner Geheimzahl eine Eins?“), und der Prüfer kann sich die Zahl zurechtbasteln. Jede Frage der Art „Wenn du diese wilde Berechnung mit deinem Geheimnis anstellt, kommt dann eine Eins heraus?“ ist unzulässig; der Prüfer könnte ja den Rechenweg – den er kennt, weil er ihn selbst vorgegeben hat – zurückgehen und, vielleicht zusammen mit den anderen bereits vorliegenden Antworten, das Geheimnis ermitteln.

Es sei denn, Zurückrechnen wäre unmöglich. Das würde heißen, man kann einen Rechenschritt nicht eindeutig umkehren. Zum Beispiel Quadrieren. Wurzelziehen ist keine eindeutige Umkehrung; es könnte ja auch die negative Wurzel gewesen sein. Dann gäbe es zwei verschiedene Geheimzahlen, die beide jedesmal die richtige Antwort produzieren, und der Prüfer wüsste nicht, ob der Beweiser die richtige oder die falsche Geheimzahl hat.

Nun stellt sich heraus: Zurückrechnen muss gar nicht grundsätzlich unmöglich sein. Es genügt, wenn es praktisch unmöglich ist. In der Sprache der Computerwissenschaftler ausgedrückt: Die Umkehrfunktion existiert zwar, ist aber nicht „effektiv“, das heißt in erträglicher Zeit, berechenbar. Solche „Einwegfunktionen“, also leicht zu berechnende Funktionen, deren Umkehrung schwer ist, dienen in der Tat als universelles Mittel für die verschlüsselte Kommunikation.

Leichte und schwere Probleme

Ein Problem ist umso schwerer, je mehr Zeit seine Lösung in Anspruch nimmt. Aber wie bestimmt man einen prinzipiellen Unterschied zwischen leichten und schweren Problemen? Was ist eine erträgliche Zeit? Eine Angabe in Sekunden ist wenig hilfreich. Stattdessen geben die Computerwissenschaftler an, wie stark der Rechenaufwand mit der Größe des Problems anwächst, und die wiederum ist definiert als die Anzahl der Zeichen (zum Beispiel Binärziffern), die man benötigt, um das Problem zu beschreiben. Die Aufgabe „Multipliziere zwei tausendstellige Zahlen“ ist also von der Größe g=2000. Eine Aufgabe, deren Rechenzeitbedarf proportional einer Potenz gn (mit einer natürlichen Zahl n) ist, gilt als leicht. Man sagt, das Ergebnis ist effektiv oder auch „in polynomialer Zeit“ berechenbar. Zum Beispiel ist beim Multiplizieren n=2. Wenn die Größe g allerdings im Exponenten steht, also zum Beispiel der Rechenzeitaufwand proportional zu 2g ist, nennt man die Aufgabe schwer.

Wenn die beiden tausendstelligen Zahlen Primzahlen sind, dann ist die Umkehrung ihrer Multiplikation eine wohldefinierte Aufgabe: Zerlege eine (sagen wir ungefähr 2000-stellige) Zahl in ihre Primfaktoren. Und während das Multiplizieren leicht ist, ist das Zerlegen („Faktorisieren“) schwer. Es gibt nämlich keinen wesentlich besseren Weg, als alle Möglichkeiten der Reihe nach durchzuprobieren, und deren Anzahl ist größenordnungsmäßig gleich einer Konstante mal 2 hoch die Anzahl der Stellen (wir denken wieder in Binärzahlen).

Wer sich auskennt (oder einen alten Artikel von Thomas Beth zum Thema liest), kann mit den folgenden Stichworten etwas anfangen: In endlichen Körpern ist die Exponentiation (f(x)=ax mit einer Konstanten a) leicht zu berechnen. Deren Umkehrung (der „diskrete Logarithmus“) ist schwer.

Ein anderes Prinzip des „ahnungslosen Beweisens“ erklärt Wigderson anhand eines mathematischen Sachverhalts aus der Graphentheorie. Ein Graph ist zunächst nur eine Sammlung von Punkten (den „Knoten“) und Strichen („Kanten“), die jeweils zwei Knoten miteinander verbinden. Es soll aber nicht darauf ankommen, wo Knoten und Kanten auf dem Papier liegen. Man darf also die Knoten beliebig hin- und herschieben, wobei die Kanten gummifädenartig mitgezogen werden, und es bleibt eigentlich derselbe Graph.

Im Computer ist dementsprechend ein Graph nichts weiter als eine Liste von Zahlenpaaren, etwa (1, 2), (1, 3), (2, 5), …, was bedeutet, dass eine Kante von Knoten Nummer 1 zu Knoten Nummer 2 verläuft, eine von 1 nach 3, eine weitere von 2 nach 5 und so weiter. Natürlich soll es nicht darauf ankommen, in welcher Reihenfolge die Knoten nummeriert sind. Das heißt, zwei Graphen (Kantenlisten) gelten auch dann als im Wesentlichen gleich („isomorph“), wenn sie durch Umnummerieren auseinander hervorgehen.

Zu entscheiden, ob zwei vorgelegte Graphen isomorph sind, ist schwer. Wenn die beiden nicht offensichtlich nicht-isomorph sind (unterschiedliche Gesamtzahl von Knoten, von Kanten oder so), bleibt einem nämlich nicht viel anderes übrig, als sämtliche Permutationen der Zahlen von 1 bis n (Anzahl der Knoten) daraufhin durchzuprobieren, ob bei einer dieser Umnummerierungen des ersten Graphen der zweite herauskommt.

Angenommen, jetzt kommt ein genialer Meister, dessen Rechenfähigkeiten wir nicht kennen, legt zwei Graphen vor und behauptet, sie seien erstens nicht isomorph, und zweitens könne er das beweisen. Aber er will den Beweis nicht herausrücken. Wie können wir mit unseren beschränkten Fähigkeiten – wir können nur leichte Probleme lösen – uns trotzdem davon überzeugen, dass seine Behauptung zutrifft?

Das geht relativ einfach. Nennen wir die beiden Graphen G und H. Wir (der Prüfer) werfen eine Münze, wählen abhängig vom Ergebnis entweder G oder H aus und nummerieren die Knoten des gewählten Graphen irgendwie um, mit einer Permutation, die wir ebenfalls zufällig auswählen. Den so errechneten Graphen K legen wir dem Beweiser vor und fragen „Zu welchem der beiden Graphen G und H ist er isomorph?“

Wenn er die richtige Antwort gibt, uns also auf den Kopf zusagt, wie die Münze gefallen ist, dann ist das zumindest ein Indiz für die Richtigkeit seiner Behauptung. Die Permutation anzuwenden ist leicht, sie ausfindig zu machen ist schwer. Der Beweiser hat also gezeigt, dass er die schwere Aufgabe lösen kann. Wenn er mit seiner ersten Behauptung gelogen hat, dann sind sowieso alle drei Graphen, G, H und K, isomorph, und die Antwort auf unsere Frage kann bestenfalls geraten sein.

Natürlich kann er, mit Wahrscheinlichkeit 50 Prozent, richtig geraten haben. Aber jetzt wiederholen wir das Frage-Antwort-Spiel, sagen wir hundertmal. Damit sinkt die Wahrscheinlichkeit, dass der Beweiser gelogen hat, auf 2–100, und wenn uns das nicht reicht, fragen wir noch ein paarmal. Vor allem aber: Dieser Beweis ist echt zero-knowledge! Denn aus den Antworten des Beweisers haben wir nur gelernt, was wir längst wussten, nämlich das Ergebnis des jeweiligen Münzwurfs, und sonst gar nichts.

Es bleibt also ein beliebig kleines Restrisiko. Damit könnte eine Bank ohne weiteres leben. Wenn aber das Geheimnis in einem mathematischen Satz besteht: Würden wir den Satz als korrekt akzeptieren, ohne den Beweis selbst gesehen zu haben? Da müssten die Mathematiker schon sehr hart schlucken. Aber: Die Anzahl der beweisbaren Sätze wächst stark an, wenn man diese Beweismethode akzeptiert. Das könnte auf die Dauer auch den traditionell gesinnten Fachvertretern die Kröte schmackhaft machen.

Und die Reichweite dieser Erweiterung ist größer, als es auf den ersten Blick scheint. Die Probleme der theoretischen Computerwissenschaft haben es nämlich so an sich, dass man sehr häufig eines in ein anderes umrechnen kann, und zwar „leicht“, das heißt mit polynomialem Aufwand. Auf diese Weise findet sich eine praktische Bedeutung selbst für das Graphenisomorphieproblem – das nun wirklich nicht so aussieht. Neue Beweismethoden führen zur Definition neuer Problemklassen, und immer wieder stellt sich heraus, dass eine neue Klasse gleich einer anderen, altbekannten ist. Das heißt: Für gewisse Probleme, die bislang als irgendwie schwer galten (und damit zur entsprechenden Problemklasse zählten), gibt es jetzt mit den zufallsabhängigen und Frage-Antwort-Spiel-Verfahren eine neue, geschicktere Lösungsmethode.

Die wesentlichen Zutaten der neuen Verfahren sind einerseits der Zufall, andererseits die Existenz von Einwegfunktionen. Den Zufall schenkt uns die Natur in Gestalt der Ereignisse aus der Quantenmechanik, die „echten Zufall“ enthalten (und nicht nur eine Beschreibung unserer Unwissenheit). Mit den Einwegfunktionen ist es schwieriger. Es ist nicht ausgeschlossen, dass es zur Faktorisierung oder zur Berechnung des diskreten Logarithmus effektive Verfahren gibt und nur unser beschränkter Verstand uns bislang daran gehindert hat, sie zu finden. Diese Frage ist in der Kurzform „P≠NP?“ eines der noch ungelösten „Jahrtausendprobleme“. Aber dass sie mit „P=NP“ beantwortet wird, dass also alle schweren Probleme in Wirklichkeit doch leicht sind, glaubt eigentlich niemand mehr ernsthaft.

Posted by

Christoph Pöppe (Jahrgang 1953) hat Mathematik und Physik studiert und über allerlei partielle Differenzialgleichungen geforscht, bis er 1989 ziemlich plötzlich Redakteur bei „Spektrum der Wissenschaft“ wurde. Fast 30 Jahre lang hat er für diese Zeitschrift Texte bearbeitet und selbst geschrieben, vornehmlich über Mathematik und verwandte Gebiete. Nach wie vor schreibt er gelegentlich Beiträge für die Rubrik „Mathematische Unterhaltungen“. Seine Liebe zum Fach lebt er auch in allerlei geometrischen Objekten aus, die gelegentlich – in Großveranstaltungen mit vielen Beteiligten – ziemlich monumental geraten. Nebenher bietet er in einem Internet-Laden Bastelbögen für allerlei geometrische Körper an.

15 comments

  1. Christoph Pöppe schrieb (24. Nov 2021):
    > […] Null-Ahnungs-Beweis […] so, dass der Prüfer von der Richtigkeit meiner Behauptung überzeugt ist, ohne von meinem Rechenweg, meiner Argumentation, meinem Geheimnis irgendetwas in Erfahrung gebracht zu haben! […]

    > […] Wenn die beiden tausendstelligen Zahlen Primzahlen sind, dann ist die Umkehrung ihrer Multiplikation eine wohldefinierte Aufgabe: Zerlege eine (sagen wir ungefähr 2000-stellige) Zahl in ihre [beiden] Primfaktoren. Und während das Multiplizieren leicht ist, ist das Zerlegen („Faktorisieren“) schwer. […]

    Wenn ich gegenüber einem Prüfer behaupte, ich wüsste, dass eine bestimmte öffentlich bekannte (meinetwegen 2000-stellige) Zahl genau zwei Primfaktoren hat, die ich kenne (aber nicht verraten will) — welche Fragen könnte mir der Prüfer dazu stellen ??

    • Eine Idee ist, Herr Dr. Frank Wappler, die “Black Box” nach einem Ergebnis wieder und wieder zu fragen, die zentrale Idee sogar.
      Es könnte dann angenommen werden, dass die “Black Box” mathematische Lösungsverfahren kennt, die von erkennenden Subjekten, gar Kapazitäten auf ihrem Gebiet, nicht nachvollzogen werden können, aber sozusagen auf einem sehr hohen (oder : niedrigen) Signifikanzniveau korrekt sind.
      Es lag wohl eine Allegorie vor, die sich weniger an diese Primzahlengeschichte klammert, sondern allgemein denkbare, also mögliche mathematische Beweisverfahren meint, die nur Maschinen entwickeln können, die amüsanterweise im Sinne der AI mit sogenannten Monte Carlo-Methoden vorgehen.
      Sozusagen selbst nicht wissen, wie sie geleistet haben, aber angeleitet werden bestmöglich ihre Versuche zu dokumentieren.

      Mit freundlichen Grüßen
      Dr. Webbaer

    • Einfach und unmittelbar einleuchtend wären die Fragen sicherlich nicht. Und ich sehe mich nicht in der Lage, solche Fragen explizit zu konstruieren. So wie ich die Literatur verstehe, ist das allerdings möglich. Die Argumentation geht ungefähr wie folgt:
      1) Jedes NP-Problem, zum Beispiel “Finde die beiden Faktoren der (explizit angegebenen) großen Zahl N “, lässt sich in ein 3-SAT-Problem umwandeln. Das ist folgende Aufgabe: Es gibt (sehr viele) logische Variable, das heißt solche, die nur die Werte “wahr” und “falsch” annehmen können, und (sehr viele) logische Ausdrücke der Form “a oder b oder c“, wobei a, b und c jeweils eine logische Variable aus dem Sortiment oder deren Verneinung sein können. Gesucht sind jetzt Werte für alle diese logischen Variablen derart, dass alle die logischen Ausdrücke wahr werden. Das Problem ist schwer (sonst wäre es nicht in NP).
      2) Jedes 3-SAT-Problem lässt sich umwandeln in das Problem “Finde eine Dreifärbung für einen (gegebenen) Graphen”. Das heißt, versieh die Knoten eines Graphen mit drei Farben so, dass nie zwei durch eine Kante verbundene Knoten dieselbe Farbe haben. Mit vier Farben geht das immer (Vierfarbensatz), mit drei Farben keineswegs immer.
      3) Nehmen wir an, der Beweiser hat eine Dreifärbung für einen (öffentlich bekannten) Graphen. Dann kann er das mit einem Zero-Knowledge-Verfahren beweisen. Und zwar so: Der Beweiser schickt dem Prüfer die Farben aller Knoten in verschlüsselter Form, und zwar für jeden Knoten einzeln, sozusagen in einem eigenen Kästchen. Der Prüfer würfelt aus der Menge aller Kanten eine aus und verlangt die Schlüssel für die Kästchen zu den beiden Knoten, die diese Kante verbindet. Der Beweiser rückt die Schlüssel heraus, der Prüfer öffnet die Kästchen (das funktioniert, weil es kryptografische Verfahren gibt) und vergewissert sich, dass verschiedene Farben drin sind. (Wenn sie gleich sind, hat der Beweiser verloren.) Jetzt wiederholen beide das Spiel; aber bevor der Beweiser die nächste Serie Kästchen berechnet und dem Prüfer schickt, permutiert er nach dem Zufallsprinzip die Farben. Zum Beispiel rot -> grün -> blau -> rot (das heißt, was zuvor rot war, wird jetzt grün, grün wird blau und so weiter). Dadurch bekommt der Prüfer keine Information über die 3-Färbung, aber der Beweiser kann nicht mogeln, sonst würde der Prüfer doch irgendwann ein Paar gleicher Farben aufdecken.
      So, jetzt haben wir den theoretischen Weg. Aber daraus ein Sortiment von Fragen zu machen, die man einem Beweiser stellen könnte, der eine Faktorisierung hat? Tut mir leid, davon habe ich null Kenntnis (zero knowledge).

      • Christoph Pöppe schrieb (25.11.2021, 23:26 o’clock):
        > Einfach und unmittelbar einleuchtend wären die Fragen sicherlich nicht. […]

        Die Aufgabe (25.11.2021, 13:21 o’clock) anhand der gegebenen/zitierten Begriffe zu formulieren, war wesentlich leichter, als (auch nur zu versuchen,) sie zu lösen. Insofern: Vielen Dank für die Beschäftigung damit.

        > 1) Jedes NP-Problem, zum Beispiel “Finde die beiden Faktoren der (explizit angegebenen) großen Zahl N “, lässt sich in ein 3-SAT-Problem umwandeln. […]
        > 2) Jedes 3-SAT-Problem lässt sich umwandeln in das Problem “Finde eine Dreifärbung für einen (gegebenen) Graphen”. […]

        Dabei wäre zu bedenken, ob diese Umwandlungen (für einen “ehrlichen Beweiser”, der jeweils die Lösung des konkreten Anfangs-Problems besitzt) “mit erträglichem Aufwand” möglich sind;
        und: ob der Prüfer von der Äquivalenz der konkreten Problemstellungen in Unkenntnis ihrer Lösungen überzeugt werden kann (und auch das “mit erträglichem Aufwand”).

        Es bleibt dann noch “die Aufabe”:
        Wenn ich gegenüber einem Prüfer behaupte, ich wüsste zu einem öffentlich bekannten Graphen eine Dreifärbung, die ich aber nicht verraten will — welche Fragen könnte mir der Prüfer dazu stellen ??

        > Und zwar so: Der Beweiser schickt dem Prüfer die Farben aller Knoten in verschlüsselter Form, und zwar für jeden Knoten einzeln, sozusagen in einem eigenen Kästchen. Der Prüfer würfelt aus der Menge aller Kanten eine aus und verlangt die Schlüssel für die Kästchen zu den beiden Knoten, die diese Kante verbindet.

        > Der Beweiser rückt die [genau zwei] Schlüssel heraus […]
        > Jetzt wiederholen beide das Spiel; aber [ … der Beweiser permutiert … ] nach dem Zufallsprinzip die Farben.

        Es erscheint deshalb wichtig, dass der Beweiser in jedem “Spiel” nur nach den zwei Knoten bzw. verschlüsselten Kästchen entsprechend genau einer (frei wählbaren bzw. erwürfelten) Kante fragen darf.
        (Dürfte er zwei Kanten begutachten, dann ließe sich mit einer, konstant gehaltenen die jeweilige Permutation herausfinden, und durch Variation der anderen würden die Färbungs-Beziehungen des Graphen schrittweise enthüllt.)

        > der Prüfer öffnet die Kästchen (das funktioniert, weil es kryptografische Verfahren gibt) und vergewissert sich, dass verschiedene Farben drin sind. (Wenn sie gleich sind, hat der Beweiser verloren.) […] der Beweiser kann nicht mogeln, sonst würde der Prüfer doch irgendwann ein Paar gleicher Farben aufdecken.

        Aber auch ein “Beweiser”, der mogeln will und muss, weil er gar keine Lösung kennt, könnte ja vermutlich “mit erträglichem Aufwand” eine Färbung der Knoten finden, in der nur sehr wenige Kanten Enden gleicher Farbe haben; und auch etliche verschiedene solche “falsche, aber nahezu richtige” Färbungen.
        (Da auch so ein “mogelnder Beweiser” erfährt, welche Kanten der Prüfer jeweils schon überprüft hat, könnte er anfangen “taktisch zu denken”, unter der Annahme, dass der Prüfer nicht einfach nur würfelt, sondern ebenfalls “taktisch denkt” …)

        Es bräuchte i.A. entsprechend viele “Spiele”, um den Prüfer zu überzeugen, dass “ich” ein ehrlicher Beweiser (aber eben kein allgemein-genialer Meister, sondern nur Besitzer einer speziellen Lösung) wäre — womöglich “unerträglich viele Spiele” …

  2. In der Sprache der Computerwissenschaftler ausgedrückt: Die Umkehrfunktion existiert zwar, ist aber nicht „effektiv“, das heißt in erträglicher Zeit, berechenbar.

    Sicher, so etwas gibt es, es ist (manchmal) die ‘Erträglichkeit der Zeit’ die einige Lösungen, auch i.p. Kryptologie verhindert.
    Wobei sog. Schlüssel auch größer werden dürfen, so dass dann, eigentlich, Hand aufs Herz!, irgendwann nichts mehr geht i.p. “Berechenbarkeit”.

    Wenn aber das Geheimnis in einem mathematischen Satz besteht: Würden wir den Satz als korrekt akzeptieren, ohne den Beweis selbst gesehen zu haben? Da müssten die Mathematiker schon sehr hart schlucken.

    In der Mathematik sind sog. Solver möglich, also denkbar, am besten sind sie so designt, dass sie se-ehr gut für erkennende Subjekt zu erklären suchen.
    Es spricht nichts gegen eine derartige Schnittstelle i.p. Explanation, außer, dass auch die Erklärung nicht verstanden wird, was zunehmender Komplexität wahrscheinlicher wird.

    Gibt es eigentlich in der Naturwissenschaft bereits Programme, die für erfasste Datenlagen Theorien ausgeben, die empirisch adäquat sind?
    (Bzw. ein sehr hohes (oder vielleicht besser : niedriges) Signifikanzniveau erreichen?)
    Hypothesen selbst entwickeln, an Hand der Datenlage, und diese zu testen wissen?

    Mit freundlichen Grüßen
    Dr. Webbaer

    • Dr. Webbaer schrieb (25.11.2021, 14:15 o’clock):
      > […] Gibt es eigentlich in der Naturwissenschaft bereits Programme, die für erfasste Datenlagen Theorien ausgeben, die empirisch adäquat sind?

      Theorien, also insbesondere die jeweilige Methodik, “Wie die betreffenden Daten erfasst wurden”, sind doch zwangsläufig von vornherein festgesetzt und ausgewählt.

      Ausgabeprodukte von Computer-Programmen (bzw. “Apps”) sind stattdessen Modelle (einschl. jeweils optimierter Parameterwerte), die die jeweilige Datenlage adäquat bis optimal zusammenfassen; vgl.
      https://en.wikipedia.org/wiki/Regression_analysis und (z.B.) https://en.wikipedia.org/wiki/Kriging

      > Hypothesen selbst entwickeln, an Hand der Datenlage, und diese zu testen wissen?

      Automatisch verschiedene vorgegebene Modell-Ansätze “durchspielen” und schlechte, insignifikante Fits verwerfen? — Schon längst.

      Weitere relevante Messgrößen (zur zusätzlichen Daten-Erhebung, und anschließender Modellierung) vorschlagen? — Das können Experten(-Systeme) leisten.

      Neue Messgrößen aus gegebenen Begriffen konstruieren, also Theorien weiterentwickeln? — Gute Frage! (Keine Ahnung, was Theoretiker den lieben langen Tag treiben …)

      Sogar ganz neue Begriffe zugrundelegen, also Paradigmen umwälzen? — Nicht mal zum Spaß.

      • Bonusfrage, Herr Dr. Frank Wappler :

        Wie genau wird eine Datenlage bearbeitet, bspw. ein Telefonbuch (das wohl bestimmte Ziffern bevorzugen wird, nicht gleichverteilt Ziffern bereit stellt), wenn sich ihr naturwissenschaftlich angenähert wird, um Sichten (“Theorien”, bei der von Ihnen geübten Unterscheidung zwischen Modellen und Theorien geht Dr. Webbaer nicht mit) zu bilden?
        Hier ist es doch so, dass am Anfang eine zu testende Hypothese, ein geeigneter Versuchsrahmen erzeugt wird, der dann bearbeitet wird, im Rahmen eines sog. Signifikanzniveaus, um dann – Am besten! – die sog. Komplementärhypothese bestätigt zu erkennen, nachdem die sog. Nullhypothese sozusagen gekillt worden ist, empiristisch?

        Und dass es nicht oder deutlich schlechter geht Datenlage ex post zu beforschen, ohne zuvor ergangene Hypothesenbildung, um dann sozusagen empirisch adäquate Theorie aus dem “Datenmist” herauszulesen?

        Mit freundlichen Grüßen
        Dr. Webbaer (den insbesondere die Unterscheidung i.p. “Ex Post” und “Ex Ante” interessiert)

  3. Bonuskommentar hierzu :

    Ich könnte meiner Bank klarmachen, dass ich meine Geheimzahl kenne, ohne dass ich sie, wie heute üblich, in irgendein mir unbekanntes Gerät eintippen müsste. Das wäre durchaus hilfreich, denn damit müsste ich nicht mehr fürchten, dass jemand das Gerät manipuliert hat, so dass er die Geheimzahl mitlesen und sich hinterher gegenüber der Bank für mich ausgeben kann.

    Um Authentifizierung zu erlangen um in der Folge autorisiert zu werden, ist es nicht möglich irgendetwas geheim zu halten, sondern es sind legitimierende Codes auszutauschen, die dann berechtigen oder nicht.
    Ein Gesicht mag ausreichen, Ausweise “kommen” idR nicht schlecht, also generell : Physikalisches.

    Es gelingt in der Regel der zu authentisierenden und idF zu autorisierenden Seite “klar zu machen”; dass der “Entry-Code”, der Autorisierung meint, stimmt.

    Dies gelingt, vglw. zuverlässig, indem das entgegen nehmende Gerät den Code bearbeitet und möglichst zeitnah einen sog. Hash generiert, der dann mit dem in der Datenhaltung vorliegenden verglichen wird, so dass sich idF Autorisierung ergeben könnte.
    Wobei das entgegen nehmende Gerät den Code nicht kennt, sondern über die Bildung eines sog. Hash zu reagieren weiß.

    Es ist unmöglich einen Code so durchzugeben, dass er nicht durchschaut sozusagen werden könnte, womöglich nagt Herr Dr. Frank Wappler so, Dr. Webbaer hat zuvörderst eine Allegorie erkannt, um die sich der werte hiesige Inhaltegeber bemüht.

    Die sozusagen sagenumwobene “Black Box”.

    Mit freundlichen Grüßen
    Dr. Webbaer

  4. Extra-Bonuskommentar hierzu :

    Wenn er die richtige Antwort gibt, uns also auf den Kopf zusagt, wie die Münze gefallen ist, dann ist das zumindest ein Indiz für die Richtigkeit seiner Behauptung. [Artikeltext]

    Dr. Webbaer hat nichts gedanklich gegen die sog. Black Box, will abär doch die Trennung, die sinnhafte, zwischen Empirie, die den Gegenstand der Naturwissenschaft meint, und der Tautologie unterschieden wissen sehend wollen.

    Wie bspw. bei derart dankenswerterweise bereit gestellter Nachricht gesehen werden kann :
    -> Frank Wappler
    25.11.2021, 16:15 o’clock

    .. ist es so, dass zwischen Mittel und Bezug, dann die sog. Naturwelt meinend, bestmöglich unterschieden werden kann.
    Die Mathematik, die Fähigkeitslehre also auf der einen Seite, auf der anderen Seite die physikalische Theoretisierung, die gerne auch empirisch adäquat sein darf, aber nicht muss (denn auch auch dann verfügt sie möglicherweise über einen Restwert sozusagen, wie die Newtonsche Physik beispielsweise, die einen Spezialfall meint).

    Bei wie genannten “Indizien” wären einige vorsichtig.

    Mit freundlichen Grüßen
    Dr. Webbaer (der auch naturwissenschaftliche Gedanken im Ablativ sozusagen mag)

    • Dr. Webbaer schrieb (25.11.2021, 16:50 o’clock):
      > Dr. Webbaer hat nichts gedanklich gegen die sog. Black Box […]

      Im Sinne einer Bonus-Bonifikation (und anstelle redundanter Grußfloskeln) möchte ich dazu einwenden:
      Es sei denn, womöglich, die betreffende Black Box beantwortete (wiederholt) den

      $ Input[ k ]: "So -- what are your outputs even supposed to mean?"

      mit

      $ Output[ k ]: "I'm afraid I don't care to tell you, Dave Doc."

      oder dergleichen.

      Die brandheißen QC-BBs sind dahingehend übrigens (bislang noch) harmlos:
      Wer rechnen kann, kann mit einigermaßen erträglichem Aufwand herausfinden, ob sie jeweils “wie gewollt” agierten, oder diesbezüglich “gestört” waren.

      • Wichtich, mittelniederdeutsch, ist es schon, Herr Dr. Frank Wappler, konsumerabel zu bleiben, eigentlich ist hier die Messbarkeit gemeint, Nachricht von A nach B verschickend meinend.
        Hinweis :
        Dr. W ist nur a bisserl soziophob, nicht sonderlich missgeleitet, mag sozusagen auch andere.

        Zum hier gemeinten Verkehr würde Dr. Webbaer gerne derart anleiten wollen, sog. Black Boxes meinend, dass besondere Gags an dieser Stelle unbenötigt bleiben und sich durchaus, im verständigen Sinne, im allgemein verständlichen Sinne, passend ableiten lässt.
        In etwa so, wie vom hiesigen wertem Inhaltegeber vorgenommen.

        Das Denken i.p. sog. Black Boxes ist IO. Dr. Webbawer bewirbt es.

        Hofft :
        Sich allgemein verständlich ausgedrückt zu haben.

        Dr. Webbaer hofft sich deutlich und klar ausgedrückt zu haben, nimmt Ihre Besonderheit, Herr Dr. Frank Wappler gerne zK, sie soll nicht den “Laden” aufhalten.

        U.a hier setzt es Minuspunkte : ‘Theorien, also insbesondere die jeweilige Methodik, “Wie die betreffenden Daten erfasst wurden”, sind doch zwangsläufig von vornherein festgesetzt und ausgewählt.’

        Mit freundlichen Grüßen
        Dr. Webbaer (der wohl einer der wenigen ist, der Sie ansatzweise versteht, abär besser ist)

  5. Sie schreiben: ‘Die Umkehrfunktion existiert zwar, ist aber nicht „effektiv“, das heißt in erträglicher Zeit, berechenbar.’

    IMHO hat sich da ein Typo eingeschlichen. Muss es nicht “effizient” statt “effektiv” heißen? Schließlich läßt sich eine nicht “effektiv berechenbare Funktion” eben nicht durch ein Turingprogramm beschreiben, ist also grundsätzlich nicht durch einen Computer berechenbar (weder in erträglicher noch unerträglicher Zeit).

  6. Welch reißerischer Titel, der Einbruch des Zufalls.
    Der Zufall ist immer gegeben, denn er ist Teil aller Möglichkeiten.
    Die Universalbibliothek von Kurd Laßwitz beinhaltet alles , was Menschen je gedacht haben und je denken werden. Die Anzahl der Bücher liegt bei 10 hoch 2 Millionen Bände. Das ganze Universum reicht nicht aus diese Zahl von bänden aufzunehmen. Die Anzahl der Atome im Universum wir nur auf 10 hoch 120 geschätzt.
    Wenn wir also Primzahlen suchen und bis heute nicht wissen, in welchem Zusammenspiel Primzahlen mit unseren natürlichen Zahlen stehen, dann sollten wir nicht vom Einbruch des Zufalls reden.
    Auf jeden Fall spielt Pi eine herausragende Rolle. Aber Pi kann durch zufälliges Werden eines Holzstabes auf parallele Linien gewonnen werden.
    Also stimmt der Titel, “Der Einbruch des Zufalls”,
    Es bleibt spannend.

Leave a Reply


E-Mail-Benachrichtigung bei weiteren Kommentaren.
-- Auch möglich: Abo ohne Kommentar. +