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 to klasa NPI zawiera nieskończenie wiele problemów[1], 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
- ↑ R. Ladner. On the structure of polynomial time reducibility, Journal of the ACM 22:155–171, 1975.
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.).