Problem NP-pośredni (, NPI) – problem decyzyjny należący do klasy NP, który nie należy ani do klasy NPC, ani do klasy P.
Jeśli to klasa NPI zawiera nieskończenie wiele problemówR. Ladner. On the structure of polynomial time reducibility, Journal of the ACM 22:155–171, 1975., a jeśli 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 ). 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
Przypisy
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
Kategoria:Klasy złożoności