Problem NP-pośredni
Z Wikipedii
W teorii złożoności obliczeniowej Problem NP-pośredni (NPI - od NP Intermediate) to problem decyzyjny należący do klasy NP, który nie należy ani do klasy NPC, ani do klasy P.
O żadnym problemie nie wiemy na pewno, że jest NP-pośredni. Jednym z kandydatów jest problem: izomorfizmu grafów. Inny znany problem: sprawdź, czy dana liczba jest pierwsza, podejrzewany o należenie do klasy NPI okazał się być problemem wielomianowym, a więc należącym do klasy P. (zob. Test pierwszości AKS).
Jeśli 
, to problemów NPI jest nieskończenie wiele1, jeśli P = NP to klasa ta jest pusta.
[edytuj] Zobacz też
[edytuj] Linki zewnętrzne
- Complexity Zoo (ang)
[edytuj] 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.
[edytuj] Przypisy
1 R. Ladner. On the structure of polynomial time reducibility, Journal of the ACM 22:155-171, 1975.
