Problem NP-pośredni

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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.

Jeśli P \neq NP, to klasa NPI zawiera nieskończenie wiele problemów[1], 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 należenie do klasy NPI, okazał się być problemem wielomianowym, a więc należącym do klasy P. (zob. Test pierwszości AKS).

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]

Literatura[edytuj | edytuj kod]

  • 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.

Przypisy

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