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

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

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

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

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

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

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

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

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

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

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

Примери

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

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

Литература

Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 978-0-7167-1045-5.