НП (класа комплексности)

Из Википедије, слободне енциклопедије

У теорији комплексности, НП (недетерминистичко полиномијално време) је скуп проблема одлучивања решивих у полиномијалном времену на недетерминистичкој Тјуринговој машини. Еквивалентно, то је скуп проблема чија решења могу да се провере на детерминистичкој Тјуринговој машини у полиномијалном времену.

Увод и примене[уреди]

Важност ове класе проблема одлучивања је у томе што садржи многе интересантне проблеме претраге и оптимизације, где желимо да утврдимо да ли постоји одређено решење за одређени проблем.

Посматрајмо на пример проблем утврђивања да ли је n сложен број. За овај проблем знамо (мада тек од 2002.) да је решив у полиномијалном времену. Међутим, аглоритам који га решава (АКС тест простости) је и даље врло тежак. Са друге стране, ако смо нашли број за који верујемо да може бити делилац за n, следећа функција нам врло брзо може рећи да ли је тај број стварно делилац, што би значило да је n сложен:

 boolean isNontrivialFactor(n, d)
     if n is divisible by d and
        d ≠ 1 and dn
         return true
     else
         return false

Ако је n сложен, ова функција ће вратити true за неки улаз d. Међутим, ако је n прост, ова функција ће увек вратити false, који год улаз d да јој проследимо. Сви проблеми у класи НП имају детерминистички алгоритам у полиномијалном времену, који, као и овај, враћа true само када му се проследе улаз и доказ да је улаз унутар језика. Овакви алгоритми проверавају потенцијална решења проблема.

Стога, изазов код НП проблема јесте да се одговор нађе на ефикасан начин, јер је ефикасан начин да се провери решење већ нађен.

Са друге старне, за општији проблем налажења броја између 1 и m који дели n (проблем факторизације) није познато да ли је у класи НП, јер још увек не постоји начин да се он реши детерминистички у полиномијалном времену.

Међу додатним примерима проблема из класе НП су:

  • Проблем изоморфизма графова, одређивање да ли се од једног графа може направити други простим преименовавањем чворова
  • Проблем трговачког путника, где покушавамо да утврдимо да ли постоји пут одређене дужине који пролази кроз све чворове неког графа
  • САТ проблем, где желимо да утврдимо да ли је нека формула исказана у буловским променљивим задовољива или не

Види чланак НП-комплетни проблеми за више важних проблема из класе НП.

Зашто је неке НП проблеме тешко решити[уреди]

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

Важан појам у овом контексту представља скуп НП-комплетних проблема одлучивања, који су подскуп класе НП, и неформално се могу описати као најтежи НП проблеми. Ако би постојао алгоритам у полиномијалном времену за макар један од њих, онда би постојао полиномијални алгоритам за све проблеме из класе НП. Због овога, и зато што до сада (упркос свим напорима) није пронађен полиномијални алгоритам ни за један НП-комплетан проблем, када се за неки проблем покаже да је НП-комплетан, обично се сматра да није вероватно да постоји полиномијални алгоритам за тај проблем.

Пример[уреди]

Проблем трговачког путника у верзији проблема одлучивања је у класи НП. Ако је дата матрица у којој су наведене раздаљине између N проблем се састоји у утврђивању да ли постоји путања која повезује све градове, укупне дужине мање од k. Недетерминистичка Тјурингова машина може да пронађе такву путању на следећи начин:

  • У сваком граду она погађа који следећи град да посети, док не посети сваки град. Ако се заглави, одмах стаје.
  • На крају проверава да ли је дужина путање мања од k за време O (n).

Свако погађање се може посматрати као прављење нове копије Тјурингове машине како би се пратио сваки могући пут напред, и ако барем једна машина нађе путању дужине мање од k, та машина прихвата улаз. (Еквивалентно, ово се може посматрати као једна Тјурингова машина која увек погађа исправно.)

Ако бисмо могли овај проблем (верзија проблема одлучивања) да решимо брзо, могли бисмо да користимо бинарну претрагу да решимо и оригинални проблем оптимизације (налажење путање и њене тачне дужине).

Литература[уреди]

  • Complexity Zoo: NP
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 34.2: Polynomial-time verification, pp. 979-983.
  • Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Sections 7.3-7.5 (The Class NP, NP-completeness, Additional NP-complete Problems), pp. 241-271.
  • David Harel, Yishai Feldman. Algorithmics: The Spirit of Computing, Addison-Wesley, Reading, MA, 3rd edition, 2004.