Az NP komplexitás megértése: meghatározás és példák

Az NP a "nemdeterminisztikus polinomidő" rövidítése. Ez egy összetettségi osztály, amely a probléma megoldásához szükséges időre utal. Az NP-ben egy algoritmus futási ideje lehet polinom a bemenet méretében, de lehet nem determinisztikus is, ami azt jelenti, hogy a futási idő az algoritmus által választott konkrét megoldástól függően változhat.

Más szóval, NP egy osztályú feladatok, amelyek polinomiális időben megoldhatók egy nem determinisztikus gépen. A nem-determinisztikus gép olyan gép, amely párhuzamosan tud egy probléma minden lehetséges megoldását kipróbálni, és elfogadja az elsőt, amelyik működik. Ez lehetővé teszi, hogy a gép sokkal gyorsabban oldjon meg néhány problémát, mint egy determinisztikus gép, amely egyszerre csak egy megoldást tud kipróbálni.

Példák az NP-ben előforduló problémákra:

* Az utazó eladó problémája (a városok listája és páronkénti távolságuk, megtalálja a lehető legrövidebb útvonalat, amely minden várost pontosan egyszer meglátogat)
* A hátizsák probléma (adott tételek halmaza, valamint súlyuk és értékeik, határozza meg az elemek azon részhalmazát, amelyet bele kell foglalni egy korlátozott kapacitású hátizsákba, amely maximalizálja a teljes értéket)
* A logikai kielégítési probléma (adott logikai változók és megszorításai, határozzuk meg, hogy létezik-e olyan érték-hozzárendelés a változókhoz, amely kielégíti az összes megkötést)

Az NP komplexitási osztály azért fontos, mert sok olyan problémát tartalmaz, amelyeket nehéz polinomban megoldani. időben, de determinisztikus géppel gyorsan ellenőrizhető. Ez azt jelenti, hogy bár egy algoritmus nem tud megoldást találni polinomiális időben, mégis hasznos lehet, ha gyorsan tudja ellenőrizni a javasolt megoldást.