Може ли проблем със SAT да бъде пълен проблем с NP?
Въпросът дали SAT (Boolean satisfiability) проблем може да бъде NP-пълен проблем е основен в теорията на изчислителната сложност. За да се отговори на това, от съществено значение е да се разгледат дефинициите и свойствата на NP-пълнотата и да се изследва историческият и теоретичен контекст, който е в основата на класификацията на SAT като NP-пълен проблем.
Дефиниции и контекст
SAT проблем: Проблемът SAT включва определяне дали съществува присвояване на стойности на истината на променливи, което прави дадена булева формула вярна. Булевата формула обикновено се изразява в конюнктивна нормална форма (CNF), където формулата е връзка на клаузи, а всяка клауза е дизюнкция на литерали. Например една формула може да изглежда така:
![\[ (x_1 \или \neg x_2) \land (\neg x_1 \or x_3) \land (x_2 \or \neg x_3). \]](https://eitca.org/wp-content/ql-cache/quicklatex.com-8e405df3b02de2e85a91e7957c82bb5b_l3.png "Предоставено от QuickLaTeX.com")
NP (недетерминирано полиномно време): Проблемът с решението е в NP, ако дадено решение може да бъде проверено като правилно или неправилно за полиномиално време от детерминирана машина на Тюринг. По същество, ако имате кандидат решение, можете да проверите неговата валидност ефективно.
NP-Пълна: Един проблем е NP-пълен, ако отговаря на две условия:
1. В НП е.
2. Всяка задача в NP може да се сведе до нея за полиномиално време.
Концепцията за NP-пълнота е въведена от Стивън Кук в неговата основна статия от 1971 г. „Сложността на процедурите за доказване на теорема“, където той демонстрира, че проблемът SAT е първият известен проблем с NP-пълнота. Този резултат сега е известен като теорема на Кук.
Теоремата на Кук и нейните последици
За да разберем защо SAT е NP-пълен, трябва да установим две ключови точки:
1. SAT е в NP.
2. Всеки проблем в NP може да бъде сведен до SAT за полиномиално време.
SAT е в NP
За да проверим дали SAT е в NP, помислете, че като се има предвид булева формула и предложено присвояване на стойности на истинност към нейните променливи, можем да проверим дали формулата се оценява на истина за полиномиално време. Това включва оценка на всяка клауза във формулата, за да се види дали поне един литерал във всяка клауза е верен. Тъй като оценяването на булева формула е лесен процес, който включва краен брой логически операции, това може да се направи ефективно. По този начин SAT е в NP, защото можем да проверим решение за полиномиално време.
Редукция на полиномно време
По-предизвикателната част от доказването, че SAT е NP-пълна, показва, че всеки проблем в NP може да бъде намален до SAT за полиномиално време. Това включва демонстриране, че за всеки проблем в NP съществува полиномиално изчислима функция, която трансформира екземпляри на проблема в екземпляри на SAT, така че оригиналният проблем да има решение, ако и само ако трансформираният екземпляр на SAT е удовлетворим.
За да илюстрираме това, помислете за общ проблем 
в НП. По дефиниция съществува недетерминирана полиномиална машина на Тюринг 
това решава . Машината има процес на полиномна проверка, който може да провери дали даден сертификат (решение) е валиден. Можем да кодираме операцията на на вход 
като булева формула, така че формулата е изпълнима тогава и само ако приема .
Кодирането включва следните стъпки:
1. Конфигурационно кодиране: Кодирайте конфигурациите (състояния, съдържание на лентата и позиции на главата) на като булеви променливи. Всяка конфигурация може да бъде представена чрез поредица от битове.
2. Преходно кодиране: Кодирайте преходната функция на като набор от булеви ограничения. Тези ограничения гарантират, че се улавят валидни преходи между конфигурации.
3. Първоначални и приемащи държави: Кодирайте първоначалната конфигурация (когато машината стартира) и приемащата конфигурация (когато машината спре и приеме) като булеви ограничения.
Чрез конструиране на булева формула, която улавя поведението на , създаваме екземпляр на SAT, който е удовлетворим, ако и само ако има последователност от валидни преходи, водещи до приемащо състояние. Това намаление може да се извърши за полиномиално време спрямо размера на входа .
Пример: Намаление от 3-SAT на SAT
За по-нататъшно изясняване на концепцията за полиномиално намаляване на времето, разгледайте специфичния случай на редуциране на 3-SAT до SAT. Проблемът 3-SAT е специален случай на SAT, където всяка клауза има точно три литерала. За да намалим 3-SAT до SAT, можем просто да наблюдаваме, че всеки екземпляр на 3-SAT вече е във формата, изисквана от SAT (т.е. CNF формула). Следователно редуцирането е тривиално и може да се направи в линейно време, което е редукция на полиномиално време.
Последици от това, че SAT е NP-пълен
Класификацията на SAT като NP-пълна има дълбоки последици за теорията на изчислителната сложност и практическото решаване на проблеми. Тъй като SAT е NP-пълен, всеки проблем в NP може да бъде преведен в екземпляр на SAT. Тази универсалност означава, че SAT служи като еталон за сложността на други проблеми. Ако можем да намерим алгоритъм с полиномиално време за решаване на SAT, можем да решим всички проблеми с NP за полиномиално време, което предполага 
.
Обратно, ако докажем, че не съществува алгоритъм за полиномиално време за SAT, това би означавало, че 
. Въпреки задълбочените изследвания, въпросът дали остава един от най-важните отворени проблеми в компютърните науки.
Практически приложения
На практика SAT решаващите се използват широко в различни области, включително проверка на софтуер, изкуствен интелект и криптография. Съвременните SAT решаващи програми използват сложни алгоритми и евристики, за да се справят ефективно с големи и сложни случаи, въпреки теоретичната NP-пълнота на SAT. Тези програми за решаване направиха възможно справянето с проблеми от реалния свят, които преди бяха неразрешими.
Заключение
Проблемът SAT наистина е NP-пълен проблем, както е установено от теоремата на Кук. Тази класификация се основава на факта, че SAT е в NP и че всеки проблем в NP може да бъде намален до SAT за полиномиално време. Последствията от това, че SAT е NP-пълен, са широкообхватни и оказват влияние както върху теоретичните изследвания, така и върху практическите приложения в компютърните науки.
Други скорошни въпроси и отговори относно Сложност:
- Класът PSPACE не е ли равен на класа EXPSPACE?
- P класът на сложност подмножество на PSPACE клас ли е?
- Можем ли да докажем, че Np и P клас са едни и същи, като намерим ефективно полиномно решение за всеки NP пълен проблем на детерминистична TM?
- Може ли класът NP да бъде равен на класа EXPTIME?
- Има ли проблеми в PSPACE, за които не е известен NP алгоритъм?
- Може ли проблемът да бъде в клас на сложност NP, ако има недетерминирана машина на Тюринг, която ще го реши за полиномиално време
- NP е класът езици, които имат полиномиални времеви верификатори
- P и NP всъщност един и същ клас на сложност ли са?
- Всеки контекстно свободен език ли е в клас на сложност P?
- Има ли противоречие между дефиницията на NP като клас задачи за решаване с верификатори за полиномиално време и факта, че проблемите в клас P също имат верификатори за полиномиално време?
Вижте още въпроси и отговори в Сложност