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

У теорији комплексности, НП-комплетни проблеми су најтежи проблеми у класи НП (недетерминистички, полиномијално време) у смислу да су најмања подкласа НП, која би евентуално могла да остане изван класе П (још увек се не зна да ли су класе П и НП једнаке). Разлог је што би детерминистичко решење било ког НП-комплетног проблема у полиномијалном времену било такође решење сваког проблема из класе НП. Класа комплексности која се састоји од свих НП-комплетних проблема се понекад назива НП-Ц. Формалнија дефиниција је дата ниже.

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

Формална дефиниција НП-комплетности уреди

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

C је НП и
C је НП-тежак проблем, то јест, сваки проблем из НП се може свести на њега.

Свести у овом контексту значи да за сваки проблем L из НП постоји детерминистички алгоритам полиномијалне сложености, који претвара случајеве l ∈ L у случајеве c ∈ C, тако да је одговор на c ДА ако и само ако је одговор на l ДА. Да се докаже да је НП проблем A НП-комплетан, довољно је показати да се неки већ познати НП-комплетан проблем своди на A.

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

Ову дефиницију је дао Стивен Кук у раду под насловом 'Комплексност процедура за доказивање теорема' на странама 151-158 Радова са трећег годишњег АЦМ симпозијума о рачунарској теорији 1971. године, мада се израз НП-комплетан није јавио у његовом раду. На тој рачунарској конференцији је вођена жестока дебата међу информатичарима око питања да ли НП-комплетни проблеми могу да се реше у полиномијалном времену на детерминистичкој Тјуринговој машини. Џон Хопкофт је успео да изнађе консензус предлогом да се питање да ли су НП-комплетни проблеми решиви у полиномијалном времену одложи за неко касније време, јер нико није имао никакав формални доказ за своје ставове. Ово је познато као питање да ли је П=НП.

Још увек нико није успео да докаже или оповргне да су НП-комплетни проблеми решиви у полиномијалном времену, тако да је ово један од великих нерешених проблема у математици. Клејов математички институтнуди награду од 1.000.000 долара ономе ко пружи формални доказ да је П=НП или да је П≠НП.

Првобитно је изгледало врло неочекивано да НП-комплетни проблеми уопште постоје, али у чувеној Кук-Левиновој теореми (коју је независно доказао и Леонид Левин), Кук је доказао да је САТ проблем НП-комплетан (једноставнији, али ипак прилично захтеван доказ овога је доступан). 1972. Ричард Карп је доказао да је још неколико проблема такође НП-комплетно (види Карпов 21 НП-комплетан проблем); и да стога постоји класа НП-комплетних проблема (и да САТ проблем није усамљен у њој). Карпу је било знатно лакше да докаже НП-комплетност за овај 21 проблем, јер ако је за неки скуп проблема већ доказано да су НП-комплетни, за нови проблем је довољно доказати да је из класе НП, и да је неки НП комплетан проблем могуће свести на њега. Од Куковог САТ проблема, за хиљаде других проблема је показано да су НП-комплетни; многе од ових проблема су сакупили Гери и Џонсон 1979. у књизи Computers and Intractability: A Guide to NP-Completeness.

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

Примери проблема уреди

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

Интересантан пример је проблем изоморфизма графова, проблем из теорије графова, који се састоји у откривању да ли постоји изоморфизам графова између два графа. Два графа су изоморфна ако се један може претворити у други простим преименовавањем чворова. Посматрајмо следећа два проблема:

Изоморфизам графова: Да ли је граф G₁ изоморфан графу G₂?
Изоморфизам подграфова: Да ли је граф G₁ изоморфан подграфу графа G₂?

Изоморфизам подграфова је НП-комплетан проблем. За изоморфизам графова се сматра да није ни П, нити НП-комплетан, мада је очигледно у класи НП. Ово је пример проблема за који се сматра да је тежак, али не довољно да би био НП-комплетан.

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

За још примера НП-комплетних проблема погледати списак НП-комплетних проблема.

Десно је дијаграм неких проблема и редукција које се обично користе да се докаже њихова НП-комплетност. На овом дијаграму, стрелица од једног проблема ка другом означава смер редукције. Ове стрелице нису показатељ математичких односа између ових проблема, јер се у полиномијалном времену сваки од ових проблема може свести на сваки други; стрелице само показују најлакши пут за свођење са једног проблема на други.

Често постоји врло мала разлика између П проблема и НП-комплетног проблема. На пример, 3-САТ проблем је НП-комплетан, док је њему врло сличан 2-САТ проблем из класе П (прецизније, НЛ-комплетан проблем), а мало општији проблем, максимални 2-САТ проблем је опет НП-комплетан. Провера да ли се граф може обојити помоћу 2 боје је П, а помоћу 3 боје је НП-комплетан проблем, чак и кад се ограничимо на планарне графове. Провера да ли је граф цикличан или бипартитан је врло лака (класе Л), али налажење максималног бипартитног или максималног цикличног графа је НП-комплетан проблем. Решавање проблема ранца унутар било ког фиксног процентуалног опсега од оптималног решења се може спровести у полиномијалном времену, али је проналажење оптималног решења НП-комплетно.