NP-Complete; ndigkeit - Matematikai lexikon

Matematikai lexikon: NP-teljesség

Az NP-hiányos problémákkal foglalkozó elmélet.

ndigkeit

Még mindig nyitott kérdés, hogy az NP és P komplexitási osztályok különböznek-e egymástól.

Általában az NP ≠ P hipotézist feltételezzük, mivel az NP = P feltételezésből nagyon valószínűtlen következtetéseket lehet levonni. Ha NP ≠ P, akkor nem lehetnek polinomiális algoritmusok (polinomiális algoritmus) az NP-teljes és az NP-nehéz problémákra (NP-nehéz probléma). Az NP-vel kapcsolatos problémák esetében az NP-teljesség igazolása a mai szempontból a legerősebb jel arra, hogy a probléma nem szerepel P-ben. Cook tételében (Cook, Tétele) először bizonyították, hogy egy probléma NP-teljes. A probléma NP-teljességének igazolásához az NP-ben elegendő egy polinomiális időcsökkentést adni az NP-teljes problémáról a vizsgált problémára. A fontos ismert NP-teljes problémák listája több ezer bejegyzést tartalmaz.

Az NP-teljesség elmélet a komplexitáselmélet legfontosabb ága, az alkalmazások számára is.