- Problem
- rozwiązanie
- podsumowanie
Jeśli spędzasz czas w społeczności programistycznej lub wokół niej prawdopodobnie często słyszysz określenie „P kontra NP”. Niestety, nawet wielu z formalnym wykształceniem informatycznym ma słabe zrozumienie tego pojęcia.
oto proste i zwięzłe wyjaśnienie:
Problem
p vs.NP problem P vs. NP pyta, Czy każdy problem, którego rozwiązanie może być szybko zweryfikowane przez komputer, może być również szybko rozwiązany przez komputer., (Wikipedia)
więc zastanówmy się, co rozumiemy przez P i NP.
problemy P są łatwo rozwiązywane przez komputery, a problemy NP nie są łatwo rozwiązywalne, ale jeśli przedstawisz potencjalne rozwiązanie, łatwo jest zweryfikować, czy jest poprawne, czy nie.
jak widać na powyższym diagramie, wszystkie problemy P są problemami NP. Oznacza to, że jeśli komputer jest łatwy do rozwiązania, łatwo jest zweryfikować rozwiązanie. Tak więc problem P vs NP jest tylko pytanie, czy te dwa typy problemów są takie same, lub jeśli są one różne, to znaczy, że istnieją pewne problemy, które są łatwo zweryfikowane, ale nie łatwo rozwiązać.,
obecnie wydaje się, że P ≠ NP, co oznacza, że mamy wiele przykładów problemów, na które możemy szybko zweryfikować potencjalne odpowiedzi, ale których nie możemy szybko rozwiązać. Spójrzmy na kilka przykładów:
- podróżujący sprzedawca chce odwiedzić 100 różnych miast, prowadząc, rozpoczynając i kończąc podróż w domu. Ma ograniczony zapas benzyny, więc może przejechać tylko 10 000 kilometrów. Chce wiedzieć, czy może odwiedzić wszystkie miasta bez benzyny., (z Wikipedii)
- rolnik chce zabrać na rynek 100 arbuzów o różnych masach. Musi spakować arbuzy do pudełek. Każde pudełko może pomieścić tylko 20 kilogramów bez łamania. Rolnik musi wiedzieć, czy 10 pudełek wystarczy, aby zanieść wszystkie 100 arbuzów na rynek. (z Wikipedii)
wszystkie te problemy mają wspólną cechę, która jest kluczem do zrozumienia intrygi P kontra NP: aby je rozwiązać, trzeba wypróbować wszystkie kombinacje.
rozwiązanie
dlatego odpowiedź na P vs., Problem NP jest tak ciekawy dla ludzi. Gdyby ktoś był w stanie pokazać, że P jest równe NP, sprawiłoby to, że trudne problemy w świecie rzeczywistym byłyby trywialne dla komputerów.
podsumowanie
- P vs.NP zajmuje się luką między komputerami mogącymi szybko rozwiązywać problemy, a po prostu być w stanie przetestować proponowane rozwiązania pod kątem poprawności.
- problem P vs. NP polega na poszukiwaniu sposobu rozwiązania problemów, które wymagają wypróbowania milionów, miliardów lub bilionów kombinacji bez konieczności wypróbowywania każdej z nich.,
- rozwiązanie tego problemu miałoby głęboki wpływ na informatykę, a tym samym na nasze społeczeństwo.
7 lutego 2017-Dodano przypisania do Wikipedii.
2 marca 2014-Poprawiono niektóre wyjaśnienia, aby uniknąć nieporozumień.