problem P kontra np, w pełnym wielomianie kontra nondeterministyczny problem wielomianowy, w złożoności obliczeniowej (dziedzina Informatyki Teoretycznej i matematyki), pytanie, czy wszystkie tak zwane problemy NP są rzeczywiście problemami P. Problem P to taki, który można rozwiązać w „czasie wielomianowym”, co oznacza, że algorytm istnieje dla jego rozwiązania tak, że liczba kroków w algorytmie jest ograniczona wielomianową funkcją n, gdzie n odpowiada długości wejścia dla problemu., W związku z tym problemy P są uważane za łatwe lub tractable. Problem nazywa się NP, jeśli jego rozwiązanie można odgadnąć i zweryfikować w czasie wielomianowym, a nondeterministyczny oznacza, że nie stosuje się żadnej konkretnej reguły do odgadnięcia.

problemy programowania liniowego są NP, ponieważ liczba kroków w metodzie simplex, wynalezionej w 1947 roku przez amerykańskiego matematyka George ' a Dantziga, rośnie wykładniczo wraz z wielkością wejścia. Jednak w 1979 roku rosyjski matematyk Leonid Chaczian odkrył wielomianowy algorytm czasu—tj.,, liczba kroków obliczeniowych rośnie jako potęga liczby zmiennych, a nie wykładniczo-pokazując tym samym, że problemy programowania liniowego są w rzeczywistości P. odkrycie to pozwoliło na rozwiązanie problemów wcześniej nierozwiązywalnych.

problem jest np-trudny, jeśli algorytm jego rozwiązania można zmodyfikować, aby rozwiązać dowolny problem NP—lub dowolny problem P, ponieważ problemy P są podzbiorem problemów NP. (Nie wszystkie problemy np-hard należą jednak do klasy problemów NP.) Problem, który jest zarówno np, jak i np-hard, mówi się, że jest np-kompletny., Tak więc znalezienie efektywnego algorytmu dla dowolnego problemu np-zupełnego implikuje, że skuteczny algorytm można znaleźć dla wszystkich problemów NP, ponieważ rozwiązanie dla dowolnego problemu należącego do tej klasy można przekształcić w rozwiązanie dla każdego innego członka klasy., W 1971 roku amerykański informatyk Stephen Cook udowodnił, że problem spełnialności (problem przypisywania wartości zmiennym we wzorze w algebrze Boole ' a takich, że twierdzenie jest prawdziwe) jest NP-zupełny, co było pierwszym problemem pokazanym jako np-zupełny i otworzyło drogę do pokazania innych problemów, które należą do klasy np-zupełnych problemów. Znanym przykładem problemu np-complete jest problem traveling salesman, który ma szerokie zastosowanie w optymalizacji harmonogramów transportu., Nie wiadomo, czy algorytmy czasu wielomianowego kiedykolwiek zostaną znalezione dla NP-zupełnych problemów, a ustalenie, czy problemy te są tractable lub trudne pozostaje jednym z najważniejszych pytań w informatyce teoretycznej. Takie odkrycie udowodniłoby, że P = NP = NP-uzupełnia i rewolucjonizuje wiele dziedzin informatyki i matematyki.

na przykład współczesna kryptografia opiera się na założeniu, że iloczyn dwóch dużych liczb pierwszych nie jest P., Zauważ, że sprawdzenie iloczynu dwóch liczb pierwszych jest łatwe (czas wielomianowy), ale obliczenie dwóch czynników pierwszych jest trudne. Odkrycie skutecznego algorytmu faktoringu dużych liczb złamałoby większość nowoczesnych schematów szyfrowania.

w 2000 roku amerykański matematyk Stephen Smale opracował wpływową listę 18 ważnych problemów matematycznych do rozwiązania w XXI wieku. Trzecim problemem na jego liście był problem P kontra NP., Również w 2000 roku został uznany za problem Milenijny, jeden z siedmiu problemów matematycznych wybranych przez Clay Mathematics Institute w Cambridge, Massachusetts, USA, do Nagrody Specjalnej. Rozwiązanie każdego problemu Milenijnego jest warte milion dolarów.