Kas mäletate, mis on NP-täielik probleem? Kuidas see erineb lihtsalt NP-st?

NP (mitte-deterministlik polünoomiline aeg) — see on probleemide klass, mille lahendust saab kontrollida polünoomilise ajaga. Teisisõnu, kui teil on vastuse kandidaat, saate kiiresti kontrollida, kas see on õige või mitte.

NP-täielikud probleemid on NP alamklass, mis on samal ajal ka kõige "raskemad" selles klassis. Kui keegi leiaks polünoomilise algoritmi mis tahes NP-täie probleemi lahendamiseks, siis kõik NP probleemid saaksid lahendada polünoomilise ajaga.

Peamine erinevus:

• NP — probleemid, mille lahendusi saab kiiresti kontrollida.
• NP-täielikud — probleemid NP-s, millele saab vähendada mis tahes teise NP probleemi (st. need on "kõige keerulisemad" NP-s).

Näide: maksimaalse kliki probleem graafis on NP-täielik, ning probleem, kas elementide alamkogu summa võrdub antud arvuga, on NP-s.