НП-тешки проблеми

НП-тешки проблеми (недетерминистички у полиномијалном времену тешки), представљају класу проблема у рачунарству, који се неформално називају тешки најмање као НП проблеми. Проблем је НП-тежак ако и само ако постоји НП-комплетан проблем такав да је полиномијално сводљив на . Другим речима, може бити решен у полиномијалном времену помоћу пророчке машине са пророчиштем за . Неформално, можемо да замислимо алгоритам који може да позове такву пророчу машину као субрутину за решавање , и да реши у полиномијалном времену, ако се позив субрутине извршава у једном кораку. НП-тешки проблеми могу бити било ког типа: проблеми одлучивања, проблеми претраге, проблеми оптимизације.

Као последица овакве дефиниције, имамо следеће исказе (ово нису дефиниције):

• проблем је најмање онолико тежак као , јер се може користити да се реши ;

• како је НП-комплетан проблем, и стога најтежи у класи НП, је такође најмање онолико тежак као НП, али он не мора да буде у класи НП, и стога не мора да буде проблем одлучивања;

• како се НП-комплетни проблеми могу сводити један на други у полиномијалном времену (полиномијална трансформација), следи да се сви НП-комплетни проблеми могу у полиномијалном времену свести на , и стога се сви проблеми из класе НП могу свести на ;

• ако постоји полиномијални алгоритам за било који НП-тежак проблем, онда постоји полиномијални алгоритам за све проблеме у класи НП, и стога је П = НП;

• ако П ≠ НП, тада НП-тешки проблеми немају решење у полиномијалном времену, али П = НП не значи аутоматски да НП-тешки проблеми могу бити решени у полиномијалном времену;

• ако оптимизациони проблем има НП-комплетну верзију проблема одлучивања , тада је НП-тежак;

• ако је из НП класе, тада је такође НП-комплетан проблем;

Честа грешка је да се мисли да НП из НП-тешки проблеми значи неполиномијални. Мада постоје широко распрострањене сумње да не постоје полиномијални алгоритми за ове проблеме, ово није доказано.

Примери

Пример НП-тешког проблем је проблем збира подскупа (проблем одлучивања), који гласи: ако је дат скуп целих бројева, да ли постоји непразан подскуп овог скупа, такав да збир његових чланова даје нулу? Ово је да/не питање, и такође је НП-комлетно. Још један пример НП-тешког проблема је оптимизациони проблем проналажења најјефтинијег пута кроз све чворове тежинског графа. Овај проблем је познат под именом проблем трговачког путника.

Постоје и проблеми одлучивања који су НП-тешки, али нису НП-комплетни, на пример халтинг проблем. Овај проблем гласи: ако је дат програм, и његов улаз, да ли ће се програм зауставити, или ће се бесконачно извршавати? Ово је да/не питање, и стога је проблем одлучивања. Лако је доказати да је халтинг проблем НП-тежак, али да није НП-комплетан. На пример, Буловски САТ проблем се може свести на халтинг проблем трансформисањем на опис Тјурингове машине која испробава све истинитосне вредности и када нађе једну комбинацију која задовољава формулу стаје, док у супротном улази у бесконачну петљу. Такође је лако видети да халтинг проблем није НП, јер су сви проблеми из класе НП одлучиви у коначном броју операција, док халтинг проблем у општем случају није.

Литература