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


13

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.).

Czy to nie jest całkowicie oparte na opiniach?
David Richerby

6
Myślę, że to dobre pytanie. Podobne, owocne pytania dotyczące mathoverflow: mathoverflow.net/questions/47214/… . mathoverflow.net/questions/56547/applications-of-mathematics .
usul

1
również nieco podobny do „opisu stołu TCS” . imho moim ulubionym jest istnienie twardych funkcji udowodnionych przez Shannona, ale prawie żadnych konstruktywnych dowodów na jakieś szczególne twarde funkcje po ponad 1/2 wieku ....
dniu

1
Istnienie quinesów jest zawsze fajne dla programistów.
Denis

2
może powinna to być wiki społeczności?
Suresh Venkat

Odpowiedzi:


9

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.


4
Nie sądzę, by wiadomo, że twardość faktoringu sugeruje bezpieczeństwo RSA.
Sasho Nikolov

1
To była znacząca luka w mojej wiedzy o kryptografii. Dzięki za zwrócenie na to uwagi; Zredagowałem swoją odpowiedź.
Philip White

1
Jeśli jesteś zainteresowany, możesz spojrzeć na to: crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf . Jednak twój przykład był dobry, nawet jeśli szczegóły były niepoprawne. Dla Diffie-Hellmana równoważność dziennika dyskretnego jest znana dla wielu grup cyklicznych, prawdopodobnie obejmujących te stosowane w praktycznych zastosowaniach: citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.78.3339 . Ponadto Diffie-Hellman jest łatwiejszy do wyjaśnienia niż RSA, IMO
Sasho Nikolov

5

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:

  • ax12+bx2+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 ... :-)


4

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.

NPNP


3

ulubione zebrane stąd i gdzie indziej


2
także inny bardzo ważny algorytm z pewnymi głębokimi kątami TCS: Pagerank
vzn
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.