Gegenintuitive Ergebnisse für Studenten

14

Ich suche nach Beispielen für Ergebnisse, die gegen die Intuition der Menschen für ein allgemeines Publikumsgespräch verstoßen. Ergebnisse, die, wenn Sie von Nicht-Experten gefragt werden, "Was sagt Ihnen Ihre Intuition?", Fast alle falsch machen würden. Die Aussage der Ergebnisse sollte für Studierende in cs / math leicht zu erklären sein. Ich suche hauptsächlich Ergebnisse in der Informatik.

Was sind die intuitivsten / unerwartetsten Ergebnisse (von allgemeinem Interesse) in Ihrer Region?

Anonym
quelle
1
Der zweite von Sashos Links ist ein Duplikat, oder?
Huck Bennett
Ähnlich, aber nicht gleich. Ich bin auf der Suche nach interessanten und nicht intuitiven Ergebnissen für allgemeine Cs / Math-Studenten, nicht für Forscher. ZB IP = PSPACE wäre keine gute Antwort.
Anonym
4
Bei ausreichend großen Eingabegrößen kann die Primalität immer in kürzerer Zeit als festgelegt werden der schnellste bekannte Weg, um eine nicht zu vernachlässigende Chance zu haben, einen RSA-Modul zu faktorisieren.

Antworten:

25

Für ein allgemeines Publikum muss man die Dinge bleiben , dass sie sehen . Sobald Sie anfangen zu theoretisieren, starten sie ihre Handys.

Hier sind einige Ideen, die ausgearbeitet werden könnten, um Beispiele zu vervollständigen:

  1. Es gibt eine Oberfläche, die nur eine Seite hat .
  2. Eine Kurve kann ein ganzes Quadrat füllen .
  3. Es gibt andere Kurven mit konstanter Breite als einen Kreis.
  4. Es ist möglich, die Ebene mit drei Farben so einzufärben, dass jeder Randpunkt ein Dreirand ist .

Wenn Sie sich auf ein wenig mathematisches Wissen verlassen können, können Sie mehr tun:

  1. Es gibt so viele ungerade Zahlen wie natürliche Zahlen.
  2. Es gibt eine kontinuierliche und nirgends differenzierbare Funktion .
  3. Es gibt eine Funktion die bei allen rationalen Zahlen diskontinuierlich und bei allen irrationalen Zahlen differenzierbar ist.f:RR
  4. Das Banach-Tarski "Paradox" .

Für Programmierer können Sie versuchen:

  1. Die unmöglich Funktionalen : Es ist ein Programm , das ein Prädikat nimmt p : stream → bool, wo streamder Datentyp der unendlichen binärer Sequenzen ist, und kehrt , truewenn und nur wenn p αist truefür alle Ströme α(das ist unzählbar viele), und aus falseanderen Gründen .

  2. Es ist möglich, Poker auf vertrauenswürdige Weise telefonisch zu spielen, um Betrug zu verhindern.

  3. Eine Gruppe von Personen kann ihr Durchschnittsgehalt berechnen, ohne dass jemand das Gehalt einer anderen Person herausfindet.

  4. Es ist ein Programm , das einen Konstrukt binären Baum T mit den folgenden Eigenschaften:

    • der Baum ist unendlichT
    • Es gibt kein Programm, das einen unendlichen Pfad in T
Andrej Bauer
quelle
Das Banach-Tarski-Paradoxon (und verwandte Paradoxe) hat mit Vorstellungen (und Manipulationen) der Unendlichkeit zu tun, was selbst professionelle Mathematiker falsch machen können (oder nicht sehr einverstanden sind) :)
Nikos M.
4
Einverstanden, aber es ist die Art unseres Satzes, die das Interesse der Menschen weckt. Es gibt ihnen einen Ruck und lässt sie an ihrer eigenen Intuition über die Unendlichkeit zweifeln.
Andrej Bauer
17

Eine Idee ist etwas Einfaches aus Streaming-Algorithmen . Der wahrscheinlich beste Kandidat ist der Mehrheitsalgorithmus. Angenommen, Sie sehen einen Strom von Zahlen , einer nach dem anderen, und Sie wissen, dass eine Zahl mehr als die Hälfte der Zeit vorkommt, aber Sie wissen nicht, welche. Wie können Sie die Mehrheitszahl finden, wenn Sie sich nur an zwei Zahlen gleichzeitig erinnern können ? Die Antwort ist der Misra-Gries-Algorithmus.s1,,sn

In jedem Zeitschritt speichern Sie eine Zahl aus dem Stream und einen Frequenzzähler f . Zu Beginn setzen Sie x auf die erste Nummer des Streams und initialisieren die Frequenz f auf 1. Wenn Sie dann eine neue Nummer s i sehen , überprüfen Sie, ob x = s i ist . Wenn x = s i , Erhöhung f zu f + 1 , verringert sonst f bis f - 1 . Wenn f = 0 , setze x auf s ixfxfsix=six=siff+1ff-1f=0xsichund zurück zu 1 . Wenn nach dem letzten Element des Streams ein Mehrheitselement vorhanden war, ist es gleich x .f1x

Eine weitere Idee ist das bekannte Spiel zur Veranschaulichung von wissensfreien Beweisen . Ich denke, es liegt an Oded Goldreich und ist ähnlich wie der wissensfreie Beweis für die Graphisomorphie.

Um die Antwort in sich geschlossen zu machen, hier ist das Spiel. Angenommen, Sie möchten Ihren farbenblinden Freund davon überzeugen, dass Sie Rot von Grün unterscheiden können. Ihr Freund hat zwei Kartenspiele und weiß, dass ein Stapel grün und der andere rot ist. Er macht Folgendes, ohne dass Sie ihn sehen: Mit Wahrscheinlichkeit 1/2 zieht er eine Karte aus jedem Stapel, mit Wahrscheinlichkeit 1/4 zieht er zwei Karten aus dem linken Stapel und mit Wahrscheinlichkeit 1/4 zieht er zwei Karten aus dem rechten Stapel . Dann zeigt er Ihnen die Karten und fragt Sie, ob sie die gleiche Farbe haben. Wenn Sie nicht farbenblind sind, können Sie natürlich jedes Mal richtig antworten. Wenn Sie farbenblind sind, werden Sie mit der Wahrscheinlichkeit 1/2 scheitern. Wenn das Spiel nun 10 Mal gespielt wird, ist die Wahrscheinlichkeit, dass Sie jedes Mal gewinnen können, wenn Sie farbenblind sind, äußerst gering.

Der Kicker ist, wenn dein Freund wüsste, dass die beiden Kartenspiele zwei verschiedene Farben haben, aber nicht wüsste, welches rot und welches grün ist, wird er es am Ende immer noch nicht wissen! Also zusammenfassend:

  1. In Beweisen ist Platz für Zufälligkeit.
  2. Sie können jemanden davon überzeugen, etwas zu wissen, ohne ihm Informationen zu geben.
Sasho Nikolov
quelle
3
Neben Misra-Gries finde ich auch die Probenahme im Reservoir einfach, aber nett.
Juho
1
@Juho ich stimme zu. Eine beliebte Interviewfrage zum Booten :).
Sasho Nikolov
13

Das Volumen einer Einheitskugel der Dimension wächst zuerst mit n ( 2 , π , 4 π / 3 , ), nimmt jedoch für n = 6 ab und konvergiert schließlich gegen 0, wenn n .nn2,π,4π/3,n=60n

Denis
quelle
1
Und der Grund dafür ist die willkürliche Entscheidung, Kugeln mit Einheitsradius im Gegensatz zu einem anderen Längenparameter zu berücksichtigen. Insbesondere nehmen die Volumina der Kugeln mit dem Durchmesser 1 von Anfang an ab.
Emil Jeřábek unterstützt Monica am
Es gibt viele interessante, eingängige Fakten über Geometrie in großen Dimensionen. Nehmen Sie zum Beispiel den Einheitshyperwürfel und schreiben Sie eine Kugel, die alle Seiten berührt. Wie weit ist eine Ecke des Hyperwürfels von der Kugel entfernt? (Antwort: Sie divergiert mit Dimension zu . Der Radius der Kugel beträgt 0,5 , aber der Abstand von der Mitte zur Ecke des Würfels beträgt 0,5 0.5 .)0.5n
usul
10

Ein kontraintuitives Ergebnis der Komplexitätstheorie ist der PCP-Satz:

Informell heißt es , dass für jeden Problem A , gibt es eine effiziente randomisierte Turing - Maschine , den Beweis Korrektheit (Nachweis der Mitgliedschaft in verifizieren kann A ) unter Verwendung von logarithmisch Anzahl von Zufallsbits und nur konstante Anzahl von Bits aus dem Beweis zu lesen. Die Konstante kann auf 3 Bit reduziert werden. Daher muss der randomisierte Prüfer nur drei Bits aus dem proklamierten Beweis lesen.NPAA

Mohammad Al-Turkistany
quelle
Was ist die Referenz für "kann auf 3 Bits reduziert werden"?
Ryan
2
Das ist bekannt als Håstad's 3-Bit (oder 3-Query) PCP-Theorem, und es muss die perfekte Vollständigkeit geopfert werden
Joe Bebel,
1
Hier finden Sie weitere Informationen und den Verweis auf Håstad's Artikel: people.csail.mit.edu/madhu/papers/1998/glst.pdf
Mohammad Al-Turkistany
6
@JoeBebel Eigentlich gibt es 3-Bit-Prüfer mit perfekter Vollständigkeit. Hastads Verifizierer ist "linear": Er tastet drei Bits ab und nimmt deren XOR. Für einen solchen Prüfer müssen Sie die perfekte Vollständigkeit opfern. Übrigens gibt es PCP-Beweise, die nur zwei Bits lesen (wiederum unbedingt ohne vollständige Vollständigkeit). Zum Beispiel siehe meine Antwort hier cstheory.stackexchange.com/a/20549/4896
Sasho Nikolov
9

Eine Sache, die sich für CS-Studenten als nicht intuitiv erweist, ist die Tatsache, dass man die auswählen kann ich-te Ordnung Statistik aus einem unsortierten Array von n Elemente in Ö(n)Zeit. Alle Schüler denken, dass sie zuerst das Array sortieren müssen (inO(n lg n) time).

Massimo Cafaro
quelle
7

building on MdBs answer/ angle, a classic result of something counterintuitive at the time of discovery in TCS at its foundations is the existence of (un)decidability itself. at the turn of the 20th century Hilbert, mirroring the thinking of other leading mathematicians of the time, thought that mathematics could be systematized (somewhat in the form of what we now recognize as algorithmic) & somewhat via the concept of "finitism" (which has rough parallels to the idea of an algorithm as a finite sequence of steps). he proposed famous open problems along these lines. his (and others) intuition turned out to be wrong in a sort of spectacular way. the counterproof is Godels theorem and Turings Halting problem. both were initially extremely abstract concepts/ results and long, highly technical papers/ arguments only understandable to leading mathematicians of the time, but now are refined to simpler conceptual structures and taught to undergraduates. these were not initially seen as two aspects/face of the same phenomenon but now they are.

also it took close to ~¾ of a century to prove that integer Diophantine equations are undecidable, Hilberts 10th problem. this is counterintuitive in the sense that it was always known that number theory was extremely difficult but the concept that some specific/ identifiable problems in it may actually be "impossible to resolve" was nearly shocking at the time to some. undecidability continues to be a deep challenge in math/ TCS even as we have decades of exponential increases in hardware due to Moores law and yet massive supercomputers that are in a sense still "powerless against it". some aspects of the surprise of undecidability can be found in the book Mathematics, Loss of Certainty by Klein.

vzn
quelle
2
Turing's paper was not extremely abstract/technical. It's actually quite straightforward and accessible.
Jeffε
1
fine, maybe for you, now, but how many undergraduates do you know who can follow the entire paper? did you follow it as an undergraduate? why are the full actual contents not covered in undergrad classes? why has an entire book been written analyzing that single paper? what about parts that anticipate concepts not discovered until decades later such as curry-howard correspondence, high level programming languages, etc?
vzn
3
Still, "long, highly technical papers/ arguments only understandable to leading mathematicians of the time" is not accurate wrt Turing's paper, which is orders of magnitude more accessible than Godel's papers. This answer is full of non-sequitirs. I cannot see what finitism has to do with Hilbert's program (I am certain he would not have been a finitist). What Moore's law has to do with undecidability is also a puzzle to me. Would you really expect exponentially faster hardware would solve undecidable problems?
Sasho Nikolov
3
why are the full actual contents not covered in undergrad classes? — Not enough time.
Jeffε
1
Fair enough, I did not know about Hilbert's finitism. I was only familiar with modern and much stricter notions of finitism. It would be better if you wrote a good answer rather than refer people to chat, but I somehow doubt you'd follow this advice.
Sasho Nikolov
6

It seems obvious, but from personal experience, the idea that you can estimate the median of a collection of items using a constant number of operations is a little shocking. And if that seems a little too technical, you can always convert it into a statement about polls an elections (you need 1300 people to get a sample with 3% error, regardless of the population size).

Related to this is the birthday paradox of course.

Suresh Venkat
quelle
5

Ein gutes Beispiel (das nicht in direktem Zusammenhang mit der Komplexität von Berechnungen steht) ist vielleicht die Turing-Universalität einfacher Rechenmodelle.

Zum Beispiel ist die Regel 110 effizient (schwach) universell:

Wenn ein (unendliches) Array von 0-1 (weiß-schwarzen) Zellen richtig initialisiert ist und die einfachen Substitutionsregeln gelten:

enter image description here

Wir haben einen "funktionierenden Computer"! :-)

Für die Definition von "schwach" und "effizient" und für andere Beispiele einfacher universeller Turingmaschinen siehe: Turlough Neary, Damien Woods; Die Komplexität kleiner Universal-Turingmaschinen: eine Übersicht .

Another puzzling example is the Turing completeness of the FRACTRAN "programming language":

  • the "program" is a list of fractions: (p1/q1,p2/q2,...,pn/qn);
  • given an input n find the first qi that divides n and replace nnpiqi;
  • repeat the previous step until no qi divides n.

With a suitable encoding of the input n, FRACTRAN can simulate any Turing machine.

You can also use other models, like cyclic tag systems, ant-automata, ....
The not-so-intuitive idea is that "computation" is hidden almost everywhere ... Wolfram wrote 1192 pages filled with figures and text to better express that idea in his A New Kind of Science (yes... yes... despite some critical reviews I finally bought a hard-copy of it :-)

Marzio De Biasi
quelle
3

A few good candidates off the top of my head:

  • Every NFA has an equivalent DFA

  • There exists a finite field of size p or pi where iN and i>0.

  • Public key cryptography

    • Calling to a function with encrypted arguments and receiving the desired result without revealing information about your inputs

    • RSA encrpytion

  • Reed-Solomon codes

  • Countability

    • |N|=|Z|=|N×N|=|Q|

    • The set of elements in the language {0,1} is countable, but R is uncountable (Cantor's diagonalization)

    • Cantor's Theorem: |S|<|P(S)|

  • On a more philosophical level, it astonished me that Turing machines accurately define computation

Bharadwaj Ramachandran
quelle