Problem NP-pośredni

Problem NP-pośredni (ang. NP-Intermediate, NPI) – problem decyzyjny należący do klasy NP, który nie należy ani do klasy NPC, ani do klasy P.

Jeśli $P\neq NP,$ to klasa NPI zawiera nieskończenie wiele problemów, a jeśli $P=NP,$ to klasa ta jest pusta.

Dla żadnego z często spotykanych w praktyce problemów obliczeniowych nie pokazano jeszcze, że należy do klasy NPI (przy założeniu, że $P\neq NP$). O przynależność do klasy NPI podejrzewa się m.in. problem izomorfizmu grafów.

Inny znany problem: sprawdź, czy dana liczba jest pierwsza, podejrzewany o przynależność do klasy NPI, okazał się być problemem wielomianowym, a więc należącym do klasy P (zob. test pierwszości AKS).

Zobacz też

• problem NP-trudny
• problem NP-zupełny
• test pierwszości

Literatura

• M.R. Garey, D.S. Johnson, Computers and Intractability: A guide to the Theory of NP-Completeness, W.H.Freeman and Co., San Francisco, 1979.
• Christos H. Papadimitriou: Złożoność obliczeniowa, WNT 2002.
• T. H. Cormen, C. E. Leiserson, C. Stein i R. L. Rivest: Introduction to Algorithms, The MIT Press/McGraw-Hill Company 1990 (wydanie polskie: Wprowadzenie do algorytmów, WNT 2004).
• M. Kubale: Łagodne wprowadzenie do analizy algorytmów, Gdańsk 2004.

Linki zewnętrzne

• Complexity Zoo. [dostęp 2017-05-18]. [zarchiwizowane z tego adresu (2019-08-27)]. (ang.).