НП-тешки проблеми — разлика између измена
Садржај обрисан Садржај додат
м Bot: Migrating 13 interwiki links, now provided by Wikidata on d:q1137554 (translate me) |
м ispravke; козметичке измене |
||
Ред 21:
== Примери ==
Пример НП-тешког проблем је [[проблем збира подскупа]] (проблем одлучивања), који гласи: ако је дат скуп целих бројева, да ли постоји непразан подскуп овог скупа, такав да збир његових чланова даје нулу? Ово је ''да''/''не'' питање, и такође је НП-комлетно. Још један пример НП-тешког проблема је оптимизациони проблем проналажења најјефтинијег пута кроз све чворове тежинског [[граф
Постоје и проблеми одлучивања који су НП-тешки, али нису НП-комплетни, на пример [[халтинг проблем]]. Овај проблем гласи: ако је дат програм, и његов улаз, да ли ће се програм зауставити, или ће се бесконачно извршавати? Ово је ''да''/''не'' питање, и стога је проблем одлучивања. Лако је доказати да је халтинг проблем НП-тежак, али да није НП-комплетан. На пример, [[Буловски САТ проблем]] се може свести на халтинг проблем трансформисањем на опис [[Тјурингова машина|Тјурингове машине]] која испробава све истинитосне вредности и када нађе једну комбинацију која задовољава формулу стаје, док у супротном улази у бесконачну петљу. Такође је лако видети да халтинг проблем није НП, јер су сви проблеми из класе НП одлучиви у коначном броју операција, док халтинг проблем у општем случају није.
== Литература ==
-{ {{cite book|author
[[Категорија:Класе комплексности]]
| |||