NP-Complet; ndigkeit - Lexicon of Mathematics

Lexicon of Mathematics: NP-Completeness

Teorie care se ocupă de probleme care sunt NP-complete.

lexicon

Este încă o întrebare deschisă dacă clasele de complexitate NP și P sunt diferite.

În general, se presupune ipoteza NP ≠ P, deoarece concluziile foarte puțin probabil se pot trage din ipoteza NP = P. Dacă NP ≠ P, nu pot exista algoritmi polinomiali (algoritm polinomial) pentru problemele NP-complete și NP-hard (problema NP-hard). Pentru problemele din NP, dovada completitudinii NP este din perspectiva de astăzi cel mai puternic indiciu că problema nu este conținută în P. Pentru prima dată în Teorema lui Cook (Cook, Teorema lui) s-a dovedit că o problemă este NP-completă. Pentru a demonstra completitudinea NP a unei probleme în NP, este suficient să se dea o reducere a timpului polinomial de la o problemă NP-completă la problema examinată. Lista importantelor probleme NP-complete cunoscute conține câteva mii de intrări.

Teoria completității NP este cea mai importantă ramură a teoriei complexității, de asemenea pentru aplicații.