w dniu 24 maja 2000 roku, Instytut Matematyki Clay wymyślił siedem problemów matematycznych, za które rozwiązanie każdego z problemów otrzyma 1 000 000 dolarów nagrody za rozwiązanie. Znane jako problemy Milenijne, do tej pory rozwiązano tylko jeden z siedmiu problemów.

chcesz zarobić milion dolarów, spróbuj rozwiązać jeden z tej listy. Są to problemy wymienione na milion dolarów nagrody nagrody.,

  1. Yang–Mills i Luka masowa
  2. hipoteza Riemanna
  3. Problem P vs np
  4. równanie Naviera–Stokesa
  5. hipoteza Hodge 'a
  6. hipoteza Poincaré' a
  7. hipoteza Bircha i Swinnertona-Dyera

ok, bądźmy realistami, te problemy są tutaj nie bez powodu. Dobrze zgadłeś, te problemy są trudne do rozwiązania. W rzeczywistości są one głębokie i naprawdę trudne, nie tylko do ich rozwiązania, ale nawet do zrozumienia stwierdzenia problemu. Większość wymienionych problemów wymaga solidnej wiedzy i analizy, nawet aby zrozumieć pytanie.,

przypuszczenie Poincaré ' a jest jedynym problemem, który został rozwiązany wśród tych siedmiu pytań. Problem ten jest z dziedziny topologii, która zajmuje się tym, jak obiekty pasują do siebie i ich kształt w przestrzeni. Problem ten był szczególnie związany ze sferami.

w 1904 roku francuski matematyk Henri Poincaré zapytał, czy sfera trójwymiarowa jest scharakteryzowana jako unikalna, po prostu połączona z trzema kolektorami. To pytanie, przypuszczenie Poincaré ' a, było szczególnym przypadkiem hipotezy geometrii Thurstona., Dowód Perelmana mówi nam, że każdy z trzech kolektorów zbudowany jest ze zbioru standardowych elementów, z których każdy ma jedną z ośmiu dobrze rozumianych geometrii.

https://www.claymath.org/millennium-problems

Omówmy trochę więcej tego, zanim przejdziemy do P kontra NP.

problem sformułował Henri Poincaré w 1904 roku, który w bardzo ogólnym ujęciu stwierdza, że jeśli masz obiekt bez otworów, a jego rozmiar jest dość mały i skończony, to jest to kula (lub może być wykonana w kulę). Nie dotyczy to tylko 3 wymiarów, ale wszystkich wymiarów.,

ale twierdzenie to nie zostało udowodnione dla czwartego wymiaru, dopóki Grigori Perelman nie wymyślił rozwiązania w 2003 roku, opartego na pracy Richarda Hamiltona.

Jeśli jesteś zainteresowany, oto, jak wygląda rozwiązanie milion dolarów:https://arxiv.org/abs/math/0211159

Grigori Perelman otrzymał milion dolarów i medal Fieldsa, z których oba odmówił.

co powiedzieć? Niektórzy z nas lubią rozwiązywać problemy, tylko dla zabawy z ich rozwiązywaniem.

szczęście cieszy się procesem!,

P kontra NP jest najnowszym problemem, który został wymieniony na liście problemów Milenijnych. Problem ten został stwierdzony w 1971 roku.

dokładne stwierdzenie problemu P kontra NP zostało wprowadzone w 1971 roku przez Stephena Cooka w jego pracy „the complexity of theorem proving procedures”.

aby poprawnie zrozumieć problem P kontra NP, niezbędna jest podstawowa znajomość złożoności obliczeniowej. W rzeczywistości P vs NP jest najbardziej oczekiwanym problemem do rozwiązania w informatyce., Tak więc dobry uchwyt tego, jak ten problem wpływa na środowisko obliczeniowe, pomoże nam przetrawić ten problem.

Jeśli jesteś nowy w temacie złożoności obliczeniowej lub złożoności w ogóle, gorąco zachęcam do zapoznania się z moją poprzednią historią na temat „Co to jest złożoność obliczeniowa?”

większość problemów w przestrzeni obliczeniowej można zredukować do problemu decyzyjnego. Oznacza to problemy, w których odpowiedź brzmi TAK lub nie.

więc wróćmy do pytania, co to jest P? a co to jest NP?,

zarówno P, jak i NP można uznać za zbiór problemów, które są pogrupowane w oparciu o to, jak trudne jest rozwiązanie i ocena rozwiązania. Termin trudny jest szczególnie ważny w tym kontekście, co zasadniczo oznacza, że jak obliczeniowo intensywny jest problem, aby rozwiązać i sprawdzić rozwiązanie.

na przykład rozważmy problem mnożenia. Jest to stosunkowo łatwy problem do rozwiązania. Nie tylko, że ten problem jest łatwy do rozwiązania, można to również zweryfikować z taką samą łatwością, po prostu mnożąc liczby., Zasadniczo każdy problem, który można rozwiązać w czasie wielomianowym, a wynik którego można zweryfikować w czasie wielomianowym, znajduje się w zbiorze złożoności p.

p ( czas wielomianowy) zawiera wszystkie problemy decyzyjne, które można rozwiązać za pomocą deterministycznej maszyny Turinga za pomocą wielomianowej ilości czasu obliczeniowego lub czasu wielomianowego.

istnieje inny zestaw problemów, które można zweryfikować w czasie wielomianowym, ale aby rozwiązać ten problem, zajmie to więcej niż czas wielomianowy. Na przykład, weźmy Sudoku na przykład., Biorąc pod uwagę, że mamy rozwiązanie dla każdej gry, możemy je łatwo zweryfikować. Oznacza to, że część weryfikacyjną możemy wykonać w czasie wielomianowym. Ale aby rozwiązać zagadkę, potrzebujemy więcej czasu. Również wraz ze wzrostem liczby siatek, złożoność znajdowania rozwiązania rośnie wykładniczo.

np (nondeterministic polynomial time) jest klasą złożoności używaną do klasyfikacji problemów decyzyjnych. NP jest zbiorem problemów decyzyjnych, dla których instancje problemu, gdzie odpowiedź brzmi „tak”, mają dowody weryfikowalne w czasie wielomianowym., (po prostu może być wielomianowo duży, nie większy)

warto zauważyć, że każdy problem, który jest w P, jest również częścią NP. Ale to może być lub nie może być imadło-versa. Oto, gdzie pitch – in myślenia badawczego. Tak więc rozwiązanie problemów NP jest powolne, ale można je szybko zweryfikować. Czy możemy poprawić szybkość rozwiązania?

przyjrzyjmy się problemowi pierwszeństwa. Test pierwszości jest algorytmem do określania, czy liczba wejściowa jest pierwsza.,

dana liczba naturalna n, czy n jest pierwsza?

problem ten był uważany za problem w podzbiorze NP, dopóki test pierwszości AKS nie udowodnił, że problem ten znajduje się pod P.,

test pierwszości AKS (znany również jako Agrawal–Kayal–Saxena primality test i cyklotomiczny test AKS) jest deterministycznym algorytmem potwierdzającym pierwotność stworzonym i opublikowanym przez Manindra Agrawal, Neeraj Kayal i Nitin Saxena, informatyków z indyjskiego Instytutu Technologii Kanpur, w dniu 6 sierpnia 2002 roku w artykule zatytułowanym „PRIMES is in P”

czy istnieje możliwość rozwiązania wszystkich problemów w np w P?, A może jest zestaw problemów, które zawsze będą trudne do znalezienia rozwiązania, aby P i NP zawsze pozostały oddzielone? Odpowiedź jest nieznana. W rzeczywistości, to jest problem za milion dolarów.

jeśli łatwo jest sprawdzić, czy rozwiązanie problemu jest poprawne, czy łatwo jest również rozwiązać problem?

typowe dla problemów NP jest to, że Hamiltonian Path Problem: biorąc pod uwagę N miast do odwiedzenia, jak można to zrobić bez odwiedzenia miasta dwa razy? Jeśli dasz mi rozwiązanie, mogę łatwo sprawdzić, czy jest poprawne. Ale nie mogę tak łatwo znaleźć rozwiązania.,

Zobacz: https://www.claymath.org/millennium-problems/p-vs-np-problem

niektóre problemy w NP można pogrupować jako np complete. Jest to grupa problemu, gdzie jeśli szybkie rozwiązanie jednego z jednego problemu znajduje możemy rozwiązać grupę problemu w tym samym zestawie złożoności z łatwością.

problem jest np-kompletny, gdy może być rozwiązany przez ograniczoną klasę algorytmów wyszukiwania brute force i może być użyty do symulacji każdego innego problemu z podobnym algorytmem.,

kompletność NP jest szczególnie ważna w dyskusji P versus NP jako rozwiązanie w czasie P, ponieważ problem w NP-complete set dowodzi, że cały zbiór złożoności upadnie. Co oznacza, że np-Complete = NP = p

problem np-complete będzie w NP i będzie w NP-Hard co oznacza, że ten problem jest co najmniej tak trudny jak każdy problem w NP, jak pokazano poniżej.,

problem jest np-trudne, jeśli algorytm do rozwiązania go można przetłumaczyć na jeden do rozwiązania dowolnego problemu np (nondeterministycznego czasu wielomianowego). Np-hard oznacza więc „przynajmniej tak twardy jak każdy problem NP”, chociaż w rzeczywistości może być trudniejszy.

istnieją problemy poza NP, które są trudne do rozwiązania w tym samym czasie trudne do sprawdzenia rozwiązania, jak również, na przykład, rozważyć szachy., Biorąc pod uwagę dowolną pozycję na pokładzie trudno jest znaleźć najlepszy następny ruch również trudno jest zweryfikować następny ruch być dokładne lub nie. Ten problem jest w EXP (wykładnicza złożoność czasu) i może poza NP.

większość badaczy z dziedziny teorii złożoności obliczeniowej uważa, że P nie jest równe NP. Event choć istnieje wiele ciekawych problemów w NP, które wpływają na nasze dzisiejsze życie jak problemy optymalizacji. Rozwiązanie pełnego problemu NP, takiego jak fałdowanie białek, oznacza, że będziemy znacznie bliżej znalezienia lekarstwa na raka., Ponadto, jeśli P = NP to możemy znaleźć kryptografię klucza publicznego do złamania, ponieważ zależy to od faktoryzacji całkowitej, która jest problemem w NP i zależy nam na tej twardości dla rozwiązania większości naszej kryptografii. Zatem implikacje udowodnienia N = NP są mieszane.

włożono wiele badań w udowodnienie albo P = NP, albo vise-versa. Ale ten problem sam w sobie wydaje się być NP-hard (po prostu sarkastyczny tutaj), ponieważ nie ma rozstrzygających wyników na teraz. Ale świat będzie o wiele ciekawszym miejscem, jeśli ktoś udowodni, że P=np., Ale jak na razie, większość dobrze wykształconych ludzi z tej dziedziny myśli inaczej.

w swoim blogu, słynny badacz computational complexity theory, Scott Aaronson stwierdza, że

Jeśli P = NP, to świat byłby głęboko innym miejscem niż zwykle Zakładamy, że jest. Nie byłoby szczególnej wartości w „kreatywnych skokach”, nie byłoby fundamentalnej luki między rozwiązaniem problemu a rozpoznaniem rozwiązania po jego znalezieniu., Każdy, kto mógłby docenić symfonię byłby Mozart; każdy, kto mógłby śledzić krok po kroku argument byłby Gauss; każdy, kto mógłby rozpoznać dobrą strategię inwestycyjną byłby Warren Buffett.

Dziękujemy za poświęcony czas.

edytowane przez Ashok Jeevan