Wyjaśnij P = problem NP do 10-latka

54

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.

Mohsin Hijazee
źródło
11
Chciałbym to zamknąć, ponieważ nie jest to teoretyczna informatyka na poziomie badawczym .
Dave Clarke
11
@Dave: Powinni na nie odpowiedzieć badacze, więc może wystarczy zapytać o miejsce, w którym idą badacze?
Jeremy
11
Myślę, że to rozsądne. Istnieje słynny artykuł zatytułowany „Jak wyjaśnić dzieciom protokoły o zerowej wiedzy”, który moim zdaniem można uznać za poziom badawczy. Prawdą jest, że może być trudno wybrać „najlepszą odpowiedź”, ale często tak jest w przypadku miękkich pytań. To pytanie może również być dobrą reklamą dla witryny, jeśli pojawią się wystarczająco interesujące odpowiedzi ... wiele osób może linkować do odpowiedzi udzielonej tutaj, gdy zostanie poproszony o wyjaśnienie P vs. NP.
Philip White
7
ale tak naprawdę powinno być CW.
Suresh Venkat
5
Poprosiłem o motywację, ponieważ sformułowanie pytania sprawiało wrażenie, że nie interesuje Cię odpowiedź na własne pytanie (wyglądało to raczej na sposób na rozpoczęcie rozmowy niż na prawdziwe pytanie), a nie dlatego, że pytanie jest głupie . Zgodnie z twoją odpowiedzią wydaje się, że zadałeś to pytanie, aby zadać pytanie, dlatego też nie jestem zainteresowany odpowiedzią na to pytanie, ponieważ to ci nie pomoże. Mamy inną kulturę niż Przepełnienie stosu, ale nie ma to teraz znaczenia.
Tsuyoshi Ito

Odpowiedzi:

33

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

Pakowanie pojemników Pakowanie pojemników jest NP kompletne 1 Pakowanie pojemników jest NP kompletne 2

Geoffrey De Smet
źródło
Bardzo łatwy do zrozumienia.
toto
4
Myślę, że „nie ma łatwego sposobu” należy rozszerzyć na skalowanie, ponieważ liczba bloków staje się większa
Ian Ringrose
3
Bardzo fajny przykład, ale czy w literaturze nie nazywa się go problemem pakowania prostokątnego?
Mohammad Al-Turkistany
1
@ user54609 NP-complete nie oznacza, że ​​możemy zweryfikować, czy upakowanie jest optymalne w czasie wielomianowym. NP-complete oznacza, że ​​możemy zweryfikować, czy rozwiązanie jest wykonalne w czasie wielomianowym (i niekonsekwentnie znajdujemy je w czasie wielomianowym (chyba że P == NP)).
Geoffrey De Smet
1
Och, więc problemem decyzyjnym jest „czy istnieje realne rozwiązanie”. Widzę.
ithisa
21

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.

ClassCheckFindExamplePEasyEasyMultiply numbersNPEasyHard8 queens

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

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=NP

ClassCheckFindPEasyEasyNPEasyEasy
P=NP

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 .PN PNPPNP

Pratik Deoghare
źródło
3
Być może mógłbyś podsumować istotę wyjaśnień Scotta.
Dave Clarke
2
Zawsze byłem ciekawy, o co tyle zamieszania w P = NP, teraz to robię!
Lee Kowalkowski
Ponieważ P ∈ NP, może wyjaśnić, że mówisz tutaj o części NP innej niż P.
David
+1 Wiele świetnych odpowiedzi w tym wątku, ale jest to jedyna, która próbuje nawet zdefiniować, co oznaczają P i NP!
Mark E. Haase
„Jeśli możemy tak łatwo„ sprawdzić ”rozwiązanie, to dlaczego nie możemy go„ łatwo znaleźć ”? --- na to pytanie jeszcze nie ma odpowiedzi! W przeciwnym razie jest to dla mnie najlepsza odpowiedź.
19

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.

Aaron Sterling
źródło
4
Dobry. Prawdopodobnie nie ma znaczenia, że ​​faktoring jest zresztą złym przykładem (a może tak?).
Raphael
4
Faktoring był przykładem, którego Mike Sipser użył w swoim wideo „wyjaśnij P / NP publicznie” dla Clay Mathematics Institute. Sądzę, że jest dla niego wystarczająco dobry .....
Aaron Sterling
3
Problem sumy częściowej można wyjaśnić uczniom, którzy jeszcze nie uczyli się mnożenia!
Tegiri Nenashi,
16

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.

Philip White
źródło
Bardzo dobra próba, chociaż nie wiem, czy 10-latek będzie wiedział, czym jest łamigłówka sudoku.
chazisop
2
@chazisop Z doświadczenia mogę powiedzieć, że podstawowe wersje łamigłówek sudoku (tj. na siatce 4x4) zostały podane dzieciom w klasach 3 i 4 jako ćwiczenia, więc nie jest to nieuzasadnione założenie.
Bob Fraser
Dobrze, ale: 1) Upuść P i NP z wyjaśnienia. Nie mają znaczenia. 2) „bardzo szybko” tworzy złą intuicję. jest z rozsądnej intuicji „bardzo szybki”, ale wielomianowy. n1000
Raphael
1
@Mohsin, nie ma za co. @ Rafael, nie sądzę, że muszę upuścić P i NP; dziesięciolatek może po prostu zaakceptować moją definicję problemu, nie wiedząc, co oznaczają P i NP, i nie jestem pewien, jak mógłbym wyjaśnić problem bez odwoływania się do niego :). Powiedziałem też, że wolę przejrzystość niż całkowitą dokładność ... dlatego nie sądzę, że niesprawiedliwe jest stosowanie „bardzo szybkiego” i „czasu wielomianowego” zamiennie.
Philip White
Chodzi mi o to, że użycie „szybkiego” nie tworzy przejrzystości. Zakładając, że P = NP, być może „jedynym” problemem jest to, że szukamy „szybkich” algorytmów dla problemów, których nie da się rozwiązać „szybko”, a jedynie wielomianowo z wysokimi stopniami.
Raphael
8

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.

Jeremy
źródło
5

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

Shitikanth
źródło
1

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

Antonio Valerio Miceli-Barone
źródło
To nie jest odpowiedź na pytanie.
Dave Clarke
Dlaczego nie? Pytanie brzmiało: „Jak wytłumaczysz problem P = NP 10-letniemu dziecku”, a moja odpowiedź brzmi: prawidłowe wyjaśnienie, które nie wprowadza w błąd, prawdopodobnie nie istnieje. Oczywiście możesz nie zgodzić się z moją odpowiedzią, ale dlaczego twierdzisz, że nie zawiera odpowiedzi na pytanie?
Antonio Valerio Miceli-Barone
3
Moim zdaniem jest to możliwa odpowiedź, chociaż się nie zgadzam. Prawdą jest, że nie możemy bezmyślnie utożsamić P z czymś takim jak „zestaw problemów, które można skutecznie rozwiązać w prawdziwym świecie”. Nie sądzę jednak, aby wykluczało to możliwość wyjaśnienia problemu P =? NP do dziesięcioletnie dziecko na poziomie intuicyjnym. Na przykład dzieci w wieku około dziesięciu lat uczą się obszaru koła. Wszelkie rygorystyczne traktowanie obszaru wymaga dużej staranności, ale nie wyklucza to możliwości nauczenia pojęcia obszaru na intuicyjnym poziomie w użyteczny sposób.
Tsuyoshi Ito
Identyfikacja klasy złożoności z możliwymi problemami jest uproszczeniem / idealizacją podobną do tych stosowanych w innych naukach takich jak fizyka, można powiedzieć, że nawet analiza asymptotyczna jest myląca, ponieważ stałe mogą być bardzo duże, a algorytm byłby niewykonalny aby uruchomić, może tak być, ale te koncepcje są wystarczająco dobre dla wielu zadań i są przydatne w praktyce. Pytanie daje intuicję na temat tych pojęć osobom niebędącym ekspertami, nie jestem pewien, czy pierwsze wprowadzenie do nich przez osoby niebędące ekspertami musi być całkowicie dokładne lubP
Kaveh
1
[ciąg dalszy] przejdź do szczegółów i wspomnij o wadach modelu. To tylko abstrakcyjny uproszczony model matematyczny, który próbuje uchwycić niektóre aspekty intuicyjnego pojęcia. Według obecnych fizyków fizyka newtonowska jest zasadniczo niepoprawna i nie zawiera właściwych prognoz dotyczących rzeczywistości w niektórych dziedzinach, ale działa całkiem dobrze w przypadku większości zadań inżynierskich. Jakikolwiek abstrakcyjny model matematyczny koncepcji intuicyjnej / rzeczywistej jest tylko modelem, teza Cobhama o identyfikacji możliwych algorytmów decyzyjnych za pomocą nie jest inna. P
Kaveh
1

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

vzn
źródło
zobacz również sondażu NP-complete zagadki przez Kendall, Parkes, Spoerer i granie w gry z algorytmów: Algorithmic Kombinatoryczna teoria gier przez Demaine i Hearn
vzn
0

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.

Mohsin Hijazee
źródło
Może warto zaostrzyć tekst. Czy próbowałeś to przeczytać na głos?
András Salamon
Myślę, że nie należy zaostrzać wszystkiego jak matematyczne definicje.
Mohsin Hijazee
Jeśli za mocno dokręcisz tekst, normalny peole nie będzie miał wystarczającej „przestrzeni”, aby zrozumieć jedną koncepcję, zanim przejdziesz do następnej.
Ian Ringrose
Jaką decyzje problemom znane są NP-wypełnić szachownicy? Wygląda na to, że większość rozważanych problemów jest znacznie trudniejsza: mathoverflow.net/questions/27944/… . n×n
Juan Bermejo Vega
Ten link jest może bardziej wyraźny niż poprzednie: cstheory.stackexchange.com/questions/6563/…
Juan Bermejo Vega