Interesujące wyniki w TCS, które można łatwo wytłumaczyć programistom bez wiedzy technicznej

Załóżmy, że spotykasz się z programistami, którzy odbyli profesjonalne kursy programowania (/ self-think), ale nie studiowali matematyki na poziomie uniwersyteckim.

Aby pokazać im piękno TCS, chciałbym zebrać kilka fajnych wyników / otwartych pytań pochodzących z TCS, które można łatwo wyjaśnić.

Dobry kandydat do tego celu (IMHO) pokaże, że problem zatrzymania nie jest rozstrzygalny. Kolejna będzie pokazywała dolną granicę czasu sortowania opartego na porównaniu (chociaż to trochę przesuwa to, co oczekuję, że zrozumieją).

Mogę również wykorzystać pomysły z problemu Wyjaśnij P = NP do 10-latka , zakładając, że niektóre z nich nie są mu znane.

Tak więc pytania muszą być następujące:

(0. Piękna)

1. Można to wyjaśnić za pomocą (co najwyżej) matematyki w szkole średniej.
2. (najlepiej) nie na tyle trywialny, aby można go było pokazać na profesjonalnych kursach programistycznych (dla C ++ / Java / Web / itp.).

Oprócz problemu zatrzymania proponuję omówienie:

Twierdzenie Rice'a. Niektóre wyjaśnienia na Wikipedii są nieco żargonowe, ale ogólnie nie jest to trudne twierdzenie lub dowód do zrozumienia poza tym; ma duże znaczenie dla rzeczywistych koncepcji, takich jak oprogramowanie antywirusowe. Dowód jest tak samo zaangażowany jak dowód problemu zatrzymania (i faktycznie zależy od nierozstrzygalności problemu zatrzymania). Zasadniczo po prostu zrozum, że „funkcją obliczalną” jest maszyna Turinga lub program komputerowy.

Myślę, że - niezależnie od pytania P vs NP - twierdzenie Cooka-Levina (i powiązane pojęcie kompletności NP) jest kolejnym bardzo dobrym kandydatem; jeśli masz (wydajny) solver dla SAT, to masz (wydajny) solver na każdy problem w NP .... i możesz skończyć z czymś zadziwiającym przynajmniej dla mnie:

• $a x_1^2 + b x_2 + c = 0$
• rozwiązywanie Sudoku;
• znalezienie ścieżki Hamiltonian na wykresie;
• rozwiązywanie wystąpienia sumy podzbioru;
• i wiele innych (rzeczywistych) problemów ...

są w pewnym sensie „równoważnymi problemami”; więc jeśli twój szef poprosi cię o stworzenie programu do pakowania pudeł do kontenera ... możesz dać mu solver Saper ... :-)

Zabawnym przykładem i zabawnym jest nierozstrzygalność problemu układania płytek Wang. Wynik wynika bezpośrednio z nierozstrzygalności problemu zatrzymania przez prostą symulację maszyn Turinga z wykorzystaniem płytek Wanga. Co ciekawe, nierozstrzygalność problemu układania płytek dla płytek Wanga doprowadziła do pięknego rezultatu, że istnieją zestawy płytek, które układają płaszczyznę tylko nieregularnie.

Wang domyślił się, że każdy zestaw płytek, który kafelek płaszczyzny musi mieć okresowe kafelki. Dlatego przypuszczenie sugeruje, że problem kafelkowania jest rozstrzygalny. Później Burger udowodnił nierozstrzygalność problemu kafelkowania, który sugerował istnienie zestawów kafelków, które kafelkują płaszczyznę tylko nieregularnie.

$NP$$NP$

ulubione zebrane stąd i gdzie indziej

• szyfrowanie klucza publicznego / algorytm RSA , funkcje zapadni , argument liczenia Shannonów pokazujący, że większość funkcji obwodu jest trudna ; ponownie ta tajemnica:

  13.2 Większość funkcji jest trudnych, ale nie mamy złych przykładów
  Na wieczny wstyd teoretycznych informatyków na całym świecie nie ma wyraźnego przykładu rodziny [trudnych] funkcji ...

• Testy AKS Pierwotności w P , stosunkowo niedawny przełom TCS, łatwy do przekazania

• P vs NP . jednym z podstawowych sposobów na powiązanie funkcji NP są gry, np. pancernik lub soduku, oba z NP całkowitymi uogólnieniami. patrz także np . książka Fortnows . zobacz także gry wideo jako NP zakończone

• nierozstrzygalność problemu korespondencji pocztowej

• Transformacja obwodu tseityny i SAT (redukcje i kompletność NP)

• (starożytny) algorytm euklidesowy i najgorsze analizy związane z sekwencją Fibonacciego

• Zgodność Curry-Howarda między proofami a programami . nie widziałem elementarnego odniesienia do tego, ale w istocie pomysł jest dość prosty i komunikatywny

• Cztery kolorowe thm poprzez automatyczne sprawdzanie thm , przełom dla TCS