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 wiele¹, jeśli P = NP to klasa ta jest pusta.

[edytuj] Zobacz też

• Problem P
• Problem NP-zupełny
• Test pierwszości

[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

¹  R. Ladner. On the structure of polynomial time reducibility, Journal of the ACM 22:155-171, 1975.

To jest tylko zalążek artykułu związanego z informatyką. Jeśli potrafisz, rozbuduj go.