Wyjaśnij P = problem NP do 10-latka

To moje pierwsze pytanie na tej stronie. Biorę kurs magisterski z teorii obliczeń. Jak wytłumaczysz problem P = NP 10-letniemu dziecku i dlaczego ma on taką nagrodę pieniężną?

Twoje zdanie?

Zaktualizuję pytanie, gdy moja głowa się o tym wyjaśni.

Używam tych 3 slajdów, aby pokazać, dlaczego tak trudno (niemożliwe?) Wymyślić szybki algorytm dla problemu NP:

W tej rozmowie Scott Aaronson odnosi się do pytania.

TEDxCaltech - Scott Aaronson - Fizyka w 21 wieku: praca w cieniu Feynmana

Ostrzeżenie: NIE pokazuj tej rozmowy bezpośrednio swojej babci / 10-latce. dlaczego? obejrzyj to, a dowiesz się. ;-)

EDYCJA:
Daj dziecku 8 łamigłówek do rozwiązania. Daj mu również limit czasowy.

Jeśli „znajdzie” rozwiązanie, to jest jednym mądrym dzieckiem, od razu możesz zacząć uczyć go CS. :) W przeciwnym
razie pokażesz mu rozwiązanie i poprosisz, aby „sprawdził”, czy jest poprawny.

$\mathsf{P}$ to zestaw problemów, z którymi komputer może łatwo „znaleźć” rozwiązanie.

$\mathsf{NP}$ to zestaw problemów, dla których komputer nie może łatwo „znaleźć” rozwiązania, ale może łatwo „sprawdzić” rozwiązanie.

Jeśli możemy tak łatwo „sprawdzić” rozwiązanie, to dlaczego nie możemy go „łatwo znaleźć”?

W CS możesz rozwiązać problem lub udowodnić, że nikt nie może.

Jeśli ktoś wymyśli algorytm, który ułatwia „znalezienie” rozwiązań problemów NP, tabela wyglądałaby następująco: i . P=N

A jeśli ktoś udowodni, że nikt nie może znaleźć algorytmu „znajdującego” rozwiązania problemów , wówczas tabela pozostaje taka sama i .P ≠ N $\mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$

Jedną z głównych rzeczy, z których ludzie korzystają z komputerów, jest wyszukiwanie. Programy takie jak Google są nawet nazywane „wyszukiwarkami” i są używane miliony razy dziennie. Komputer niedawno pokonał ludzi w Jeopardy, ponieważ był w stanie przeszukać mnóstwo danych, bardzo szybko.

Ale niektóre rzeczy są trudne nawet dla komputerów. Brzmi dziwnie, prawda? Jednym z przykładów jest odwrotne mnożenie. Oczywiście, jeśli powiem „Co 5 razy 3?” możesz powiedzieć „15” w nanosekundach, cześć! Ale jaka jest odpowiedź na pytanie: „Które dwie liczby ze sobą połączone to 21?”. (Poczekaj na odpowiedź, 7 x 3.) Racja! Teraz, które dwie liczby pomnożone razem wynoszą 23? (Poczekaj na odpowiedź lub frustrację.)

Jedynymi dwiema liczbami pomnożonymi razem, które są równe 23, są same 1 i 23. To wymagało trochę myślenia, prawda? A 23 to niewielka liczba. Pomyśl, czy liczba składała się z setek cyfr. Chodzi o to, że najlepsze programy na świecie nie mogą odwrócić mnożenia znacznie lepiej niż 7-latek mógłby to zrobić, po prostu testując jedną liczbę, a następnie następną, a potem następną. Komputery mogą to zrobić szybciej , ale tak naprawdę nie wiemy, jak powiedzieć komputerowi, aby zrobił to mądrzej . Ludzie zdobywają doktoraty w tym zakresie i wiedzą tylko, jak powiedzieć komputerom, aby nieco odwrotnie rozmnażały się.

Więc może nie ma mądrzejszego sposobu. Ale może jest i po prostu jeszcze tego nie znaleźliśmy. To jest w skrócie problem P / NP: jeśli mogę natychmiast rozpoznać odpowiedź - 1 razy 23 to 23, hm - czy to pomaga mi szybciej szukać odpowiedzi? Ludzie myślą, że to tak ważne, że osoba, która wymyśli odpowiedź, tak lub nie, wygra milion dolarów.

Myślę, że problem P vs. NP można wyjaśnić bardzo delikatnie w odniesieniu do Sudoku. Zakładam, że ten dziesięciolatek zna Sudoku. W moich wyjaśnieniach postaram się przedkładać prostotę nad rygor.

Oto moja próba wyjaśnienia P = NP hipotetycznemu dziesięciolatkowi:

Jeśli masz zagadkę Sudoku, która nie została jeszcze ukończona, i chcesz ją ukończyć, może to być naprawdę trudne. Z drugiej strony, jeśli twój przyjaciel zakończy problem i jesteś dobry w arytmetyce, nietrudno jest sprawdzić, czy rozwiązanie twojego łamigłówki jest prawidłowe.

Pytanie P = NP pyta, czy istnieje bardzo szybki, krok po kroku proces rozwiązywania zagadki Sudoku, która nie została jeszcze ukończona. Proces krok po kroku musi być tak przejrzysty i łatwy do zrozumienia, że ​​nawet komputer może to zrozumieć i używać go do szybkiego i szybkiego rozwiązywania łamigłówek Sudoku. Jeśli istnieje tak szybki proces krok po kroku, matematycy nazywają to „algorytmem wielomianowym” (wyjaśnię, co to oznacza, gdy będziesz starszy).

W rzeczywistości informatycy i programiści zidentyfikowali wiele innych zagadek i bardzo ważnych problemów, które są tak samo trudne do rozwiązania jak Sudoku. Naprawdę ważne jest, aby wiedzieć, czy problemy te można rozwiązać, ponieważ komputery mogłyby nam pomóc szybciej wykonać wiele rzeczy. Mogą na przykład pomóc nam bardziej efektywnie planować pociągi, łamać tajne kody, a może nawet pomóc w budowie naprawdę inteligentnych komputerów zdolnych do sztucznej inteligencji.

Byłoby wiele bardzo dobrych rzeczy, które mogłyby się zdarzyć, gdyby ludzie mogli rozwiązać P = NP. Oczywiście pojawiałyby się również problemy, ponieważ trudniej byłoby używać tajnych kodów, aby utrzymać prywatne wiadomości w tajemnicy.

Większość inteligentnych matematyków uważa, że ​​P = NP nie jest prawdziwe. Innymi słowy, większość ludzi uważa, że ​​nikt nigdy nie będzie w stanie szybko rozwiązać naprawdę trudnych zagadek Sudoku. Jednak nikt nigdy nie był w stanie udowodnić, że P nie jest równy NP, więc organizacja zwana Clay Mathematics Institute oferuje nagrodę w wysokości miliona dolarów za pierwszy dowód, że P = NP jest prawdziwy, lub za pierwszy dowód, że jest to fałsz.

Jak widzicie, wziąłem nieco „dosłownie to wyjaśnić dziesięciolatkowi”. :)

Mam nadzieję że to pomoże.

Oto jak wytłumaczyłem to mojej mamie, mam nadzieję, że ci to pomoże :)

Są problemy, dla których łatwo jest znaleźć rozwiązanie (P, ale mniej nazywają je „łatwymi do rozwiązania”), problemy, dla których łatwo jest sprawdzić, czy dane rozwiązanie jest poprawne (NP, ale nazwijmy je „łatwymi do sprawdzenia” ) oraz problemy, które nie są ani łatwe do rozwiązania, ani łatwe do sprawdzenia. Dla uproszczenia załóżmy, że „łatwy” jest formalnie zdefiniowany i że każdy problem ma unikalne rozwiązanie.

Teraz ludzie byli w stanie udowodnić (używając matematyki) interesujące relacje między tymi dwoma pojęciami „łatwego do rozwiązania” i „łatwego do sprawdzenia”, tak że niektóre problemy nie są łatwe do rozwiązania, a niektóre inne nie są łatwe do sprawdzenia. Podstawowym przykładem takiego wyniku jest to, że problem, który można łatwo rozwiązać, jest również łatwy do sprawdzenia: po prostu znajdź jego rozwiązanie i porównaj z podanym rozwiązaniem.

Kusząco rzecz biorąc, dla wielu praktycznych problemów (takich jak decydowanie, czy możliwe jest przydzielenie studentów do profesorów i klas, gdy margines jest bardzo niewielki), nie wiadomo, czy istnieje „łatwy” sposób jego rozwiązania, ale wiadomo, jak łatwo sprawdzić, czy rozwiązanie jest prawidłowe, czy nie. Ludzie dużo próbowali i ponieśli porażkę, a następnie próbowali udowodnić, że nie było to możliwe i również ponieśli porażkę: po prostu nie wiedzą. Niektórzy uważają, że wszystkie problemy, które można łatwo sprawdzić, są łatwe do rozwiązania (powinniśmy tylko więcej o tym pomyśleć), inni uważają, że nie powinniśmy tracić czasu na szukanie łatwych rozwiązań tych problemów.

Dowiedzieliśmy się, jak pokazywać powiązania między problemami (np. Jeśli wiesz, jak iść do szkoły, wiesz, jak iść do piekarni, która znajduje się tuż przed nim) i problemy, które można łatwo sprawdzić, które są powiązane ze wszystkimi innymi problemami, które można łatwo sprawdzić ( NP-zupełne, ale nazwijmy je „kluczowymi problemami”) tak, że jeśli ktoś pewnego dnia pokaże, że jeden z kluczowych problemów można łatwo rozwiązać, wówczas wszystkie problemy, które można łatwo sprawdzić, są również łatwe do rozwiązania (tj. P = NP). Z drugiej strony, jeśli ktoś pokaże, że jednego z kluczowych problemów nie da się łatwo rozwiązać, to żadnego z pozostałych problemów nie da się łatwo rozwiązać (tj. P <> NP).

Pytanie jest więc kuszące i stosunkowo ważne w praktyce (choć niektórzy twierdzą, że powinniśmy raczej skupić się na alternatywnych definicjach „łatwego”), a ludzie inwestują w debatę sporo pieniędzy i czasu.

Michael Sipser wyjaśnia P vs problemu NP w bardzo intuicyjny sposób w tym filmie .

Jestem nieco sceptycznie nastawiony do możliwości wyjaśnienia tego problemu 10-latkowi, a nawet świeckiemu, bez popełniania fałszywych interpretacji kluczowych pojęć.

Wszystkie wyjaśnienia sformułowane w kategoriach „łatwości” w porównaniu z „twardością” znajdowania vs sprawdzania rozwiązań zakładają tezę Cobhama, która jest prawdopodobnie fałszywa w ogólnym przypadku i może być uznana za coś więcej niż tylko ogólną zasadę.

strategie wygrywające dla różnych klasycznych gier planszowych, np. pancernika lub (ostatnio) gier wideo, okazały się NP zakończone i jest to doskonały sposób na przedstawienie / opisanie niektórych podstawowych teorii dla początkujących.

pancernik jako NP problem z decyzją kompletną Dziennik Merlijn Sevenster ICGA wrzesień 2004

minesweeper jest NP kompletnym FAQ przez matematyka RW Kaye. Wydanie Matematyki Inteligencer z wiosny 2000 r. (Tom 22 nr 2, strony 9--15)

Granie to ciężka praca, ale ktoś musi to zrobić! artykuł arxiv autorstwa Giovanniego Viglietty. analizuje złożoność obliczeniową Pac-Man, Tron, Lode Runner, Boulder Dash, Deflektor, Mindbender, Pipe Mania, Skweek, Prince of Persia, Lemmings, Doom, Puzzle Bobble 3 i Starcraft.

Pacman to twardy artykuł o ekstremalnej technologii na powyższym papierze

A oto moje podejście do problemu.

Kido!

Wiesz, że napotykamy wiele problemów w naszym życiu. Możesz powiedzieć wyzwania. Niektóre są trudne, niektóre łatwiejsze. Na przykład często trzeba dodać dwie liczby. A ostatniego wieczora byliśmy na szachownicy i musieliśmy wygrać z sąsiadem. Cóż, dodanie dwóch liczb jest prostym i prostym problemem z ograniczonymi krokami. Takie problemy nazywane są problemami klasy P, ponieważ istnieje wiele wielu problemów, które są dość proste, z dyskretnymi krokami, które należy powtarzać w kółko, aby uzyskać rozwiązanie.

Z drugiej strony, ostatniej nocy w naszej grze w klatkę piersiową, jaka strategia byłaby najlepsza do wygrania gry? Możemy przesunąć pierwszy pionek o jeden krok, lub drugi pionek o jeden krok, lub możemy przesunąć drugi pionek o dwa kroki i pierwszy pionek o jeden krok, aby zobaczyć, że istnieje wiele możliwości. Ale czy istnieje dla nas sposób lub przepis, który daje nam kompletne uporządkowane zestawy ruchów, które dają najlepsze i matowi? Widzisz więc, że jest to dość trudne, ponieważ na każdym kroku jest tak wiele możliwości. Miliardy i miliardy, jak mówi Carl Sagan.

Ale kochanie, co jeśli powiem ci wszystkie pozycje na planszy i zapytam, czy to mat. Z pewnością będziesz w stanie szybko stwierdzić w ciągu kilku badań, czy są jakieś legalne posunięcia dla króla.

Tak więc problemy, które są trudne do rozwiązania, ale jeśli ich rozwiązanie można łatwo zweryfikować w kilku prostych krokach, nazywa się je problemami NP.

Teraz pytasz, co oznacza P = NP? Właściwie to pytanie oznacza, że ​​istnieje sposób, aby znaleźć łatwiejsze rozwiązanie dla znalezienia najlepszej strategii lub uporządkowanej listy ruchów do gry w szachy bez przechodzenia przez wszystkie miliardy możliwości, tak jak robimy to dla prostego dodatku? To proste pytanie pozostaje jeszcze bez odpowiedzi. Nie mamy żadnego dowodu na to, że jest to prawda ani na odrzucenie, ale jeśli to zrobimy, nastąpi przełom. Jeśli okaże się to prawdą, nasza cywilizacja może rozwiązać bardzo skomplikowane problemy, zamieniając je w problemy klasy P. Ludzie będą w stanie złamać hasła w ciągu kilku sekund, wiadomości zostaną odszyfrowane i wiele więcej, dlatego ten problem jest uważany za jeden z najważniejszych problemów tysiąclecia.