Кук-Левинова теорема

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

Важна последица ове теореме је да ако бисмо имали алгоритам који у полиномијалном времену решава САТ проблем, могли бисмо у полиномијалном времену да решимо сваки проблем из класе НП.

Теорему су независно доказали Стивен Кук 1971. у раду Комплексност процедура за доказивање теорема,^[1] и Леонид Левин 1972. у раду Универзални проблеми претраге.^[2] Кук је добио Тјурингову награду 1982. за овај рад.

Дефиниције

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

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

Буловски проблем задовољивости се састоји из буловских израза који комбинују буловске променљиве помоћу буловских оператора. Израз је задовољив ако постоји нека додела истинитосних вредности променљивима, тако да је цео израз тачан.

Доказ

Овај доказ је базиран на доказу који су дали Гери и Џонсон.^[3]

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

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

За сваки улаз I одређујемо буловски израз такав да је задовољив ако и само ако машина прихвата .

Буловски израз користи променљиве дате у следећој табели, где

Променљиве	Намеравана интерпретација	Колико?
	Тачно ако ћелија садржи симбол у кораку израчунавања.
	Тачно ако је глава машине над ћелијом у кораку израчунавања.
	Тачно ако је у стању у кораку израчунавања.

Дефинишимо буловски израз као конјункцију клауза из следеће табеле, за све −() :

Клаузе	Услови	Интерпретација	Колико?
	Ћелија улаза садржи симбол .	Почетни садржај траке.
		Почетно стање
	Почетна позиција главе.
		Један симбол по ћелији.
		Трака остаје непромењена ако се по њој не пише.
		Само једно стање у једном тренутку.
		Само један положај главе у једном тренутку.
Дисјункција клауза		Могући прелази у кораку израчунавања када је глава у позицији .
Дисјункција клауза	.	Мора да заврши у стању прихватања.

Ако постоји прихватајуће израчунавање за на улазу , тада је задовољив, додељивањем и интерпретацијама. Са друге стране, ако је задовољиво, онда постоји прихватајуће израчунавање за на улазу које прати кораке наведене додељивањем променљивих.

Колико је велико ? Постоји буловских променљивих, од којих свака може да буде кодирана у простору . Број клауза је . Тако да је величина једнака . Ово је полиномијално у односу на , величину улаза, па је трансформација сигурно полиномијална редукција, као што је и било захтевано.

Последице

Доказ показује да се сваки НП проблем може свести у полиномијалном времену на САТ проблем. Ово значи да ако би САТ проблем могао да се реши у полиномијалном времену на детерминистичкој Тјуринговој машини, онда би сви НП проблеми могли да се реше у полиномијалном времену, и то би значило да је класа комплексности НП једнака класи комплексности П.

Значај НП-комплетности је постао јасан 1972, издавањем чувеног рада Ричарда Карпа, Сводљивост међу комбинаторним проблемима, у коме је показано да је 21 проблем из комбинаторике и теорије графова, сваки познат по својој тежини, такође НП-комплетан.^[4]

Карп је показао да је сваки од ових проблема НП-комплетан свођењем неког другог (за који је раније показано да је НП-комплетан) на овај проблем. На пример, показао је да је 3-САТ проблем (проблем задовољивости за буловске изразе у конјуктивној нормалној форми са тачно три литерала или негације по клаузи) НП-комплетан, показавши како да се било који САТ проблем (у полиномијалном времену) сведе на 3-САТ. (Прво се користе Де Морганови закони да се формула преведе у конјуктивну нормалну форму, а затим се уведу нове променљиве да би се разбиле клаузе са више од три литерала, јер је , а клаузе са мање од три литерала се прошире новим променљивима које су гарантовано нетачне, на пример

Гери и Џонсон су представили више од 300 НП-комплетних проблема у својој књизи , а и даље се откривају нови проблеми у овој класи комплексности.^[3]