Разумевање сложености НП: дефиниција и примери

НП је скраћеница за "недетерминистичко полиномско време". То је класа сложености која се односи на количину времена потребног за решавање проблема. У НП, време рада алгоритма може бити полиномно у величини улаза, али може бити и недетерминистичко, што значи да време рада може да варира у зависности од специфичног решења одабраног од стране алгоритма.ӕӕ Другим речима, НП је класа задатака који се могу решити за полиномно време на недетерминистичкој машини. Недетерминистичка машина је машина која може паралелно испробати сва могућа решења проблема и прихватити прво које ради. Ово омогућава машини да решава неке проблеме много брже од детерминистичке машине, која може да испроба само једно решење у исто време.ӕӕНеки примери проблема у НП укључују:ӕӕ* Проблем трговачког путника (дати листу градова и њихове раздаљине у паровима, пронађите најкраћи могући пут који посети сваки град тачно једном)ӕ* Проблем са ранцем (дати скуп предмета и њихове тежине и вредности, одредите подскуп ставки које треба укључити у ранац ограниченог капацитета који максимизира укупну вредност)ӕ* Проблем логичке задовољивости (дати скуп логичких променљивих и њихова ограничења, утврдити да ли постоји додела вредности променљивим која задовољава сва ограничења)ӕӕ Класа сложености НП је важна јер укључује многе проблеме које је тешко решити полиномом времена, али се може брзо верификовати детерминистичком машином. То значи да иако алгоритам можда неће моћи да пронађе решење у полиномском времену, ипак може бити користан ако може брзо да верификује предложено решење.