Ці можа праблема SAT быць поўнай праблемай NP?

/ / Апублікавана ў кібербяспека, Асновы тэорыі складанасці вылічэнняў EITC/IS/CCTF, складанасць, Доказ таго, што SAT з'яўляецца NP поўным

Пытанне аб тым, ці можа задача SAT (Boolean satisfiability) быць NP-поўнай праблемай, з'яўляецца фундаментальным у тэорыі складанасці вылічэнняў. Для вырашэння гэтай праблемы вельмі важна разгледзець азначэнні і ўласцівасці NP-поўнасці і вывучыць гістарычны і тэарэтычны кантэкст, які ляжыць у аснове класіфікацыі SAT як NP-поўнай праблемы.

Вызначэнні і кантэкст

Праблема SAT: Праблема SAT прадугледжвае вызначэнне таго, ці існуе прысваенне значэнняў праўдзівасці зменным, якое робіць дадзеную лагічную формулу сапраўднай. Лагічная формула звычайна выражаецца ў кан'юнктыўнай нармальнай форме (CNF), дзе формула з'яўляецца кан'юнкцыяй пунктаў, а кожны пункт - дыз'юнкцыяй літэралаў. Напрыклад, формула можа выглядаць так:

    \[ (x_1 \or \neg x_2) \land (\neg x_1 \or x_3) \land (x_2 \or \neg x_3). \]

NP (недэтэрмінаваны паліномны час): Праблема прыняцця рашэння знаходзіцца ў NP, калі дадзенае рашэнне можа быць праверана як правільнае або няправільнае за палінаміяльны час дэтэрмінаванай машынай Цьюрынга. Па сутнасці, калі ў вас ёсць варыянт рашэння, вы можаце эфектыўна праверыць яго сапраўднасць.

NP-Поўны: Задача лічыцца NP-поўнай, калі яна задавальняе дзвюм умовам:
1. Гэта ў НП.
2. Кожную задачу з NP можна звесці да яе за паліномны час.

Канцэпцыя NP-поўнасці была ўведзена Стывенам Кукам у яго асноўнай працы 1971 года «Складанасць працэдур доказу тэарэм», дзе ён прадэманстраваў, што праблема SAT з'яўляецца першай вядомай задачай NP-поўнасці. Гэты вынік цяпер вядомы як тэарэма Кука.

Тэарэма Кука і яе наступствы

Каб зразумець, чаму SAT з'яўляецца NP-поўным, нам трэба ўсталяваць два ключавых моманту:
1. SAT знаходзіцца ў НП.
2. Кожная задача ў NP можа быць зведзена да SAT за паліномны час.

SAT знаходзіцца ў NP

Каб пераканацца, што SAT знаходзіцца ў NP, улічыце, што з улікам лагічнай формулы і прапанаванага прысваення значэнняў праўдзівасці яе зменным мы можам праверыць, ці дае формула праўду за паліномны час. Гэта прадугледжвае ацэнку кожнага пункта ў формуле, каб убачыць, ці праўдзівы хаця б адзін літар у кожным пункте. Паколькі ацэнка лагічнай формулы - гэта просты працэс, які ўключае канечную колькасць лагічных аперацый, гэта можа быць зроблена эфектыўна. Такім чынам, SAT знаходзіцца ў NP, таму што мы можам праверыць рашэнне за паліномны час.

Паліном-Скарачэнне часу

Больш складанай часткай доказу таго, што SAT з'яўляецца NP-поўным, з'яўляецца тое, што кожная задача ў NP можа быць зведзена да SAT за паліномны час. Гэта прадугледжвае дэманстрацыю таго, што для любой задачы ў NP існуе вылічальная функцыя паліномнага часу, якая пераўтварае асобнікі задачы ў асобнікі SAT так, што зыходная задача мае рашэнне тады і толькі тады, калі трансфармаваны асобнік SAT з'яўляецца выканальным.

Каб праілюстраваць гэта, разгледзім агульную праблему P у НП. Па вызначэнні існуе недэтэрмінаваная паліномная машына Цьюрынга M што вырашае P. Машына M мае паліномны працэс праверкі, які можа праверыць, ці сапраўдны сертыфікат (рашэнне). Мы можам закадзіраваць аперацыю M на ўваходзе x як лагічная формула такая, што формула выканальная тады і толькі тады, калі M прымае x.

Кадаванне ўключае ў сябе наступныя этапы:
1. Кадаванне канфігурацыі: Кадзіраваць канфігурацыі (станы, змесціва стужкі і пазіцыі галавы) з M як лагічныя зменныя. Кожная канфігурацыя можа быць прадстаўлена паслядоўнасцю бітаў.
2. Пераходнае кадзіраванне: Кадзіраваць функцыю пераходу M як набор лагічных абмежаванняў. Гэтыя абмежаванні забяспечваюць фіксацыю сапраўдных пераходаў паміж канфігурацыямі.
3. Першапачатковая і прымаючая дзяржавы: Закадзіруйце пачатковую канфігурацыю (калі машына запускаецца) і прымальную канфігурацыю (калі машына спыняецца і прымае) у якасці лагічных абмежаванняў.

Пабудаваўшы лагічную формулу, якая адлюстроўвае паводзіны M, мы ствараем асобнік SAT, які з'яўляецца выканальным тады і толькі тады, калі існуе паслядоўнасць сапраўдных пераходаў, якія вядуць да прымальнага стану. Гэта скарачэнне можа быць выканана за паліномны час адносна памеру ўваходных дадзеных x.

Прыклад: зніжэнне з 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 за паліномны час, маючы на ​​ўвазе P = NP.

І наадварот, калі мы дакажам, што для SAT не існуе алгарытму паліномнага часу, гэта будзе азначаць, што P \neq NP. Нягледзячы на ​​шырокія даследаванні, пытанне аб тым, ці P = NP застаецца адной з найбольш значных адкрытых праблем інфарматыкі.

Практычнае прымяненне

На практыцы вырашальнікі SAT шырока выкарыстоўваюцца ў розных галінах, уключаючы праверку праграмнага забеспячэння, штучны інтэлект і крыптаграфію. Сучасныя вырашальнікі SAT выкарыстоўваюць складаныя алгарытмы і эўрыстыкі для эфектыўнай апрацоўкі вялікіх і складаных экзэмпляраў, нягледзячы на ​​тэарэтычную NP-паўнату SAT. Гэтыя рашальнікі дазволілі вырашаць рэальныя праблемы, якія раней былі цяжкавырашальныя.

Conclusion

Праблема SAT сапраўды з'яўляецца NP-поўнай праблемай, як устаноўлена тэарэмай Кука. Гэтая класіфікацыя заснавана на тым факце, што SAT знаходзіцца ў NP і што кожная задача ў NP можа быць зведзена да SAT за паліномны час. Наступствы таго, што SAT будзе NP-поўным, маюць далёка ідучыя вынікі і ўплываюць як на тэарэтычныя даследаванні, так і на практычнае прымяненне ў інфарматыцы.

Іншыя апошнія пытанні і адказы адносна складанасць:

Больш пытанняў і адказаў глядзіце ў Complexity

Яшчэ пытанні і адказы:

тэгі: , , , , ,