Wyniki sprzeczne z intuicją dla studentów

14

Szukam przykładów wyników, które są sprzeczne z intuicją ludzi podczas ogólnej dyskusji publiczności. Wyniki, które na pytanie ekspertów niebędących ekspertami „co podpowiada ci intuicja?”, Prawie wszystko byłoby błędne. Oświadczenie o wynikach powinno być łatwe do wyjaśnienia studentom w cs / matematyce. Głównie szukam wyników w informatyce.

Jakie są najbardziej sprzeczne z intuicją / nieoczekiwane wyniki (ogólne zainteresowanie) w Twojej okolicy?

Anonimowy
źródło
1
Drugi z linków Sasho to duplikat, nie?
Huck Bennett
Podobne, ale nie takie same. Szukam wyników, które są interesujące i sprzeczne z intuicją dla studentów cs / matematyki, a nie naukowców. Np. IP = PSPACE nie byłby dobrą odpowiedzią.
Anonimowy
4
W przypadku wystarczająco dużych rozmiarów wejściowych, o pierwszeństwie zawsze można zdecydować w krótszym czasie niż najszybszym znanym sposobem, aby mieć niemałą szansę na uwzględnienie modułu RSA.

Odpowiedzi:

25

Dla ogółu odbiorców musisz trzymać się rzeczy, które mogą zobaczyć . Gdy tylko zaczniesz teoretyzować, uruchomią swoje telefony komórkowe.

Oto kilka pomysłów, które można wypracować w celu uzupełnienia przykładów:

  1. Jest powierzchnia, która ma tylko jedną stronę .
  2. Krzywa może wypełnić cały kwadrat .
  3. Istnieją krzywe o stałej szerokości inne niż okrąg.
  4. Możliwe jest pokolorowanie płaszczyzny trzema kolorami w taki sposób, że każdy punkt graniczny jest trójkątem .

Jeśli możesz polegać na odrobinie wiedzy matematycznej, możesz zrobić więcej:

  1. Jest tyle nieparzystych liczb, ile jest liczb naturalnych.
  2. Istnieje funkcja ciągła i nigdzie różna .
  3. Istnieje funkcja która jest nieciągła dla wszystkich liczb wymiernych i różniczkowalna dla wszystkich liczb niewymiernych.f:RR
  4. Banacha-Tarskiego „paradoks” .

Dla programistów możesz spróbować:

  1. W niemożliwych Funkcjonały : jest to program, który wykonuje orzeczenie p : stream → bool, w którym streamjest typ danych nieskończonych ciągów binarnych i powraca truewtedy i tylko wtedy, gdy p αjest truedla wszystkich strumieni α(to uncountably wiele), a falseinaczej.

  2. Można grać w pokera przez telefon w zaufany sposób, co zapobiega oszukiwaniu.

  3. Grupa ludzi może obliczyć swoje przeciętne wynagrodzenie bez wiedzy o wynagrodzeniach innych osób.

  4. Istnieje program, który konstruuje drzewo binarneT o następujących właściwościach:

    • drzewo jest nieskończoneT
    • nie ma programu, który śledziłby nieskończoną ścieżkę wT
Andrej Bauer
źródło
paradoks Banacha-Tarskiego (i związane z nimi paradoksy) mamy do czynienia z pojęciami (i manipulacji) nieskończoności, coś, że nawet zawodowi matematycy mogą dostać źle (lub nie wiele o nim) :)
Nikos M.
4
Zgadzam się, ale to rodzaj obraźliwego twierdzenia, które wzbudza zainteresowanie ludzi. Daje im to wstrząs i sprawia, że ​​wątpią we własne intuicje dotyczące nieskończoności.
Andrej Bauer
17

Jeden pomysł to coś prostego z algorytmów przesyłania strumieniowego . Prawdopodobnie najlepszym kandydatem jest algorytm większościowy. Załóżmy, że widzisz strumień liczb , jeden po drugim, i wiesz, że jedna liczba występuje więcej niż w połowie przypadków, ale nie wiesz, która z nich. Jak znaleźć numer większości, jeśli pamiętasz tylko dwie liczby na raz ? Odpowiedzią jest algorytm Misra-Gries.s1,,sn

Na każdym kroku zapisujesz liczbę ze strumienia i licznik częstotliwości . Na początku ustawiasz na pierwszą liczbę strumienia i inicjujesz częstotliwość na 1. Następnie, gdy zobaczysz nową liczbę , sprawdzasz, czy . Jeśli , zwiększ do , w przeciwnym razie zmniejsz do . Jeśli , zestaw do i z powrotem do . Po ostatnim elemencie strumienia, jeśli był element większości, będzie on równyf x f s i x = s i x = s i f f + 1 f f - 1 f = 0 x s i f 1 xxfxfsix=six=siff+1ff1f=0xsif1x .

Innym pomysłem jest dobrze znana gra ilustrująca zero dowodów wiedzy . Myślę, że wynika to z Oded Goldreich i jest podobny do zerowego dowodu wiedzy na temat izomorfizmu grafów.

Aby odpowiedź była samodzielna, oto gra. Załóżmy, że chcesz przekonać swojego niedowidzącego przyjaciela, że ​​możesz odróżnić czerwony od zielonego. Twój przyjaciel ma dwie talie kart i wie, że jeden stos jest zielony, a drugi czerwony. Robi to bez ciebie: z prawdopodobieństwem 1/2 losuje jedną kartę z każdej talii, z prawdopodobieństwem 1/4 losuje dwie karty z lewej talii, a z prawdopodobieństwem 1/4 losuje dwie karty z prawej talii . Następnie pokazuje ci karty i pyta, czy są tego samego koloru. Jeśli nie jesteś ślepy na kolory, możesz oczywiście odpowiedzieć poprawnie za każdym razem. Jeśli jesteś ślepy na kolory, zawiedziesz z prawdopodobieństwem 1/2. Jeśli teraz gra się 10 razy, prawdopodobieństwo, że wygrasz za każdym razem będąc ślepym na kolory, jest bardzo niskie.

Kick polega na tym, że jeśli twój znajomy wiedział, że dwie talie kart mają dwa różne kolory, ale nie wiedział, który z nich jest czerwony, a który zielony, nadal nie będzie wiedział na końcu! Podsumowując:

  1. W dowodach jest miejsce na przypadkowość.
  2. Możesz przekonać kogoś, że coś wiesz, nie przekazując mu żadnych informacji na ten temat.
Sasho Nikolov
źródło
3
Oprócz Misra-Gries uważam również, że pobieranie próbek ze zbiorników jest proste, ale przyjemne.
Juho
1
@Juho Zgadzam się. Popularne pytanie do rozmowy kwalifikacyjnej :).
Sasho Nikolov
13

Objętość sfery jednostkowej wymiaru najpierw rośnie wraz ze wzrostem ( ), ale zaczyna się zmniejszać dla i ostatecznie zbiega się do jako .n 2 , π , 4 π / 3 , n = 6 0 n nn2,π,4π/3,n=60n

Denis
źródło
1
Powodem tego jest arbitralna decyzja o uwzględnieniu kul o promieniu jednostkowym, a nie o innym parametrze długości. W szczególności objętości kulek o średnicy 1 zmniejszają się od samego początku.
Emil Jeřábek
Istnieje wiele powiązanych, zabawnych, sprzecznych z intuicją faktów na temat geometrii w wysokich wymiarach. Na przykład weź hiperłącze jednostki i wpisz kulę dotykającą wszystkich boków. Jak daleko jest róg hipersześcianu od kuli? (Odpowiedź: W miarę wzrostu wymiaru zmienia się na . Promień kuli wynosi , ale odległość od środka do rogu sześcianu wynosi .)0,5 0,5 0.50.5n
usul
10

Przeciwnie intuicyjnym wynikiem teorii złożoności jest twierdzenie PCP:

NPAA

Mohammad Al-Turkistany
źródło
Jakie jest odniesienie do „można sprowadzić do 3 bitów”?
Ryan
2
Jest to znane jako 3-bitowe (lub 3-kwerendowe) twierdzenie HPstad na PCP i wymaga poświęcenia idealnej kompletności
Joe Bebel
1
Tutaj znajdziesz dalsze informacje i odniesienie do pracy Håstad
Mohammad Al-Turkistany
6
@JoeBebel W rzeczywistości istnieją 3-bitowe weryfikatory z doskonałą kompletnością. Weryfikator Hastada jest „liniowy”: próbkuje trzy bity i pobiera ich XOR. Dla takiego weryfikatora musisz poświęcić idealną kompletność. BTW, istnieją dowody PCP, które czytają tylko dwa bity (znowu niekoniecznie bez doskonałej kompletności). Na przykład zobacz moją odpowiedź tutaj cstheory.stackexchange.com/a/20549/4896
Sasho Nikolov
9

inO(n)O(n lg n)

Massimo Cafaro
źródło
7

bazując na odpowiedzi / kącie MdB, klasycznym rezultatem czegoś sprzecznego z intuicją w momencie odkrycia w TCS u jego podstaw jest samo istnienie (nie) rozstrzygalności . na przełomie XIX i XX wieku Hilbert, odzwierciedlając myśl innych czołowych matematyków tamtych czasów, pomyślał, że matematykę można usystematyzować (nieco w formie tego, co obecnie nazywamy algorytmem ) i nieco poprzez koncepcję „finityzmu” ( który ma przybliżone podobieństwa do idei algorytmu jako skończonej sekwencji kroków). zaproponował słynne otwarte problemy w tym zakresie. jego (i inni) intuicja okazała się błędna w pewien spektakularny sposób. kontroodporność jestTwierdzenie Godelsa i problem zatrzymania Turingsa . oba były początkowo niezwykle abstrakcyjnymi pojęciami / wynikami i długimi, wysoce technicznymi artykułami / argumentami zrozumiałymi tylko dla czołowych matematyków tamtych czasów, ale teraz są dopracowane do prostszych struktur koncepcyjnych i nauczane dla studentów. nie były one początkowo postrzegane jako dwa aspekty / oblicze tego samego zjawiska, ale teraz są.

również zajęło prawie ¾ wieku, aby udowodnić, że liczby całkowite Równania diofantyczne są nierozstrzygalne, dziesiąty problem Hilberta . jest to sprzeczne z intuicją w tym sensie, że zawsze wiadomo było, że teoria liczb jest niezwykle trudna, ale koncepcja, że ​​niektóre konkretne / możliwe do zidentyfikowania problemy mogą być „niemożliwe do rozwiązania”, była dla niektórych niemal szokująca. nierozstrzygalność nadal stanowi głębokie wyzwanie w matematyce / TCS, mimo że mamy dekady wykładniczego wzrostu sprzętu ze względu na prawo Mooresa, a jednak ogromne superkomputery, które są w pewnym sensie nadal „bezsilne”. niektóre aspekty niespodzianki nierozstrzygalności można znaleźć w książce Mathematics, Loss of Certainty autorstwa Kleina.

vzn
źródło
2
Artykuł Turinga nie był zbyt abstrakcyjny / techniczny. Jest to właściwie dość proste i dostępne.
Jeffε
1
w porządku, może teraz, ale ile znasz studentów , którzy mogą śledzić cały artykuł? udało Ci śledzić go jako student? dlaczego pełne rzeczywiste treści nie są objęte klasami licencjackimi? dlaczego napisano całą książkę analizującą ten pojedynczy artykuł? co z częściami, które przewidują koncepcje odkryte dopiero po dziesięcioleciach, takie jak korespondencja curry-howard , języki programowania wysokiego poziomu itp.?
vzn
3
Jednak „długie, wysoce techniczne artykuły / argumenty zrozumiałe dla czołowych matematyków tamtych czasów” nie są dokładne w pracy Turinga, która jest o rząd wielkości bardziej dostępna niż prace Godela. Ta odpowiedź jest pełna non-sequitirs. Nie rozumiem, co ma wspólnego finityzm z programem Hilberta (jestem pewien, że nie byłby finalistą). To, co prawo Moore'a ma wspólnego z nierozstrzygalnością, jest dla mnie zagadką. Czy naprawdę spodziewałbyś się, że sprzęt wykładniczo szybszy rozwiąże nierozwiązywalne problemy?
Sasho Nikolov
3
dlaczego pełne rzeczywiste treści nie są objęte klasami licencjackimi? - Za mało czasu.
Jeffε
1
Szczerze mówiąc, nie wiedziałem o skończoności Hilberta. Znałem tylko nowoczesne i znacznie bardziej rygorystyczne pojęcia finityzmu. Byłoby lepiej, gdybyś napisał dobrą odpowiedź, niż polecał ludziom czat, ale jakoś wątpię, czy zastosowałbyś się do tej rady.
Sasho Nikolov
6

Wydaje się to oczywiste, ale z własnego doświadczenia pomysł, że można oszacować medianę zbioru przedmiotów przy użyciu stałej liczby operacji, jest nieco szokujący. A jeśli wydaje się to trochę zbyt techniczne, zawsze możesz przekonwertować je na stwierdzenie o wyborach wyborczych (potrzebujesz 1300 osób, aby uzyskać próbkę z 3% błędem, niezależnie od liczebności populacji).

Powiązany z tym jest oczywiście paradoks urodzinowy .

Suresh Venkat
źródło
5

Być może dobrym przykładem (niezwiązanym bezpośrednio ze złożonością obliczeniową) jest uniwersalność prostych modeli obliczeniowych Turinga.

Na przykład reguła 110 jest wydajnie (słabo) uniwersalna:

Biorąc pod uwagę (nieskończoną) tablicę 0-1 (biało-czarnych) komórek właściwie zainicjowanych i proste zasady podstawiania:

wprowadź opis zdjęcia tutaj

mamy „działający komputer”! :-)

Definicję „słabo” i „wydajnie” oraz inne przykłady prostych uniwersalnych maszyn Turinga można znaleźć w: Turlough Neary, Damien Woods; Złożoność małych uniwersalnych maszyn Turinga: ankieta .

Innym zagadkowym przykładem jest kompletność Turinga „języka programowania” FRACTRAN :

  • (p1/q1,p2/q2,...,pn/qn)
  • nqinnnpiqi
  • qin

n

Możesz także użyć innych modeli, takich jak cykliczne systemy tagów, ant-automaty, ... Niezbyt
intuicyjny pomysł polega na tym, że „obliczenia” są ukryte prawie wszędzie ... Wolfram napisał 1192 strony wypełnione cyframi i tekstem, aby lepiej wyrazić ten pomysł w swoim A New Kind of Science (tak ... tak ... pomimo niektórych krytycznych recenzji w końcu kupiłem jego wersję papierową :-)

Marzio De Biasi
źródło
3

Kilku dobrych kandydatów z mojej głowy:

  • Każdy NFA ma równoważny DFA

  • ppiiNi>0

  • Kryptografia klucza publicznego

    • Wywołanie funkcji z zaszyfrowanymi argumentami i otrzymanie pożądanego wyniku bez ujawnienia informacji o danych wejściowych

    • Kodowanie RSA

  • Kody Reeda-Solomona

  • Policzalność

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

    • {0,1}R

    • |S|<|P(S)|

  • Z bardziej filozoficznego punktu widzenia zadziwiło mnie, że maszyny Turinga precyzyjnie definiują obliczenia

Bharadwaj Ramachandran
źródło