Ці аднолькавы клас складанасці P і NP?
Пытанне аб тым, ці роўна P роўна NP, з'яўляецца адной з самых глыбокіх і нявырашаных праблем інфарматыкі і матэматыкі. Гэтая праблема ляжыць у цэнтры тэорыі складанасці вылічэнняў, вобласці, якая вывучае неад'емную складанасць вылічальных задач і класіфікуе іх у залежнасці ад рэсурсаў, неабходных для іх вырашэння.
Каб зразумець пытанне, неабходна зразумець азначэнні класаў P і NP. Клас P складаецца з задач прыняцця рашэнняў (задач з адказам "так/не"), якія могуць быць вырашаны з дапамогай дэтэрмінаванай машыны Цьюрынга за паліномны час. Паліномны час азначае, што час, неабходны для вырашэння задачы, можа быць выражаны як паліномная функцыя памеру ўваходных дадзеных. Прыклады задач у P ўключаюць сартаванне спісу лікаў (што можа быць зроблена за час O(n log n) з выкарыстаннем эфектыўных алгарытмаў, такіх як сартаванне зліццём) і пошук найбольшага агульнага дзельніка двух цэлых лікаў з дапамогай алгарытму Еўкліда (які працуе ў O(log (мін(а, б))) час).
Клас NP, з іншага боку, складаецца з задач рашэння, для якіх дадзенае рашэнне можа быць праверана за палінаміяльны час дэтэрмінаванай машынай Цьюрынга. Гэта азначае, што калі нехта прапануе варыянт рашэння задачы, можна эфектыўна праверыць яго правільнасць. Важна адзначыць, што NP не абавязкова азначае, што сама праблема можа быць вырашана за паліномны час, толькі тое, што прапанаванае рашэнне можа быць праверана хутка. Прыклады праблем у NP ўключаюць праблему лагічнай выканальнасці (SAT), дзе імкнуцца вызначыць, ці існуе прысваенне значэнняў праўдзівасці зменным, што робіць дадзеную булеву формулу праўдзівай, і праблему гамільтанава цыклу, якая пытаецца, ці існуе цыкл які наведвае кожную вяршыню графа роўна адзін раз.
Пытанне P супраць NP задаецца пытаннем, ці можна кожную задачу, рашэнне якой можна праверыць за палінаміяльны час (г.зн. кожную задачу ў NP), таксама вырашыць за палінаміяльны час (г.зн. знаходзіцца ў P). Фармальна пытанне ў тым, ці P = NP. Калі б P было роўна NP, гэта азначала б, што кожная задача, для якой можна хутка праверыць рашэнне, таксама можа быць хутка вырашана. Гэта будзе мець сур'ёзныя наступствы для такіх галін, як крыптаграфія, аптымізацыя і штучны інтэлект, паколькі многія праблемы, якія цяпер цяжка вырашаць, патэнцыйна могуць стаць эфектыўна вырашальнымі.
Нягледзячы на дзесяцігоддзі даследаванняў, пытанне P супраць NP застаецца адкрытым. Ніхто яшчэ не змог даказаць, што P = NP або P ≠ NP. Складанасць гэтай задачы падкрэсліваецца тым, што яна была ўключана Інстытутам матэматыкі Клея ў лік сямі «Праблем тысячагоддзя» з прэміяй у 1 мільён долараў за правільнае рашэнне. Адсутнасць дазволу прывяла да значных падзей як у тэарэтычнай, так і ў прыкладной інфарматыцы.
Адным з ключавых паняццяў, звязаных з пытаннем P супраць NP, з'яўляецца NP-паўната. Задача з'яўляецца NP-поўнай, калі яна знаходзіцца ў NP, і такой жа складанай, як і любая задача ў NP, у тым сэнсе, што любая задача NP можа быць зведзена да яе з дапамогай паліномнага скарачэння часу. Канцэпцыя NP-поўнасці была ўведзена Стывенам Кукам у яго асноўнай працы 1971 года, дзе ён даказаў, што задача SAT з'яўляецца NP-поўнай. Гэты вынік, вядомы як тэарэма Кука, быў наватарскім, таму што даў канкрэтны прыклад NP-поўнай задачы і ўсталяваў структуру для ідэнтыфікацыі іншых NP-поўных задач.
З тых часоў было паказана, што многія іншыя задачы з'яўляюцца NP-поўнымі, такія як праблема гандляра, праблема клікі і праблема заплечніка. Значэнне NP-поўнасці заключаецца ў тым, што калі любая NP-поўная задача можа быць вырашана за палінаміяльны час, то кожная задача ў NP можа быць вырашана за палінаміяльны час, што азначае P = NP. І наадварот, калі любая NP-поўная задача не можа быць вырашана за паліномны час, то P ≠ NP.
Каб праілюстраваць канцэпцыю NP-паўнаты, разгледзім задачу гандляра (TSP). У гэтай задачы прадавец павінен наведаць набор гарадоў, кожны роўна адзін раз, і вярнуцца ў зыходны горад з мэтай мінімізацыі агульнай адлегласці падарожжа. Версія рашэння TSP пытаецца, ці існуе тур па гарадах з агульнай адлегласцю меншай або роўнай зададзенаму значэнню. Гэтая праблема ў NP, таму што, улічваючы прапанаваны тур, можна лёгка праверыць за паліномны час, ці адпавядае тур абмежаванню адлегласці. Больш за тое, TSP з'яўляецца NP-поўным, таму што любую праблему ў NP можна пераўтварыць у асобнік TSP за паліномны час.
Іншым прыкладам з'яўляецца праблема клікі, якая пытаецца, ці змяшчае дадзены граф поўны падграф (кліку) зададзенага памеру. Гэтая праблема ў NP, таму што, улічваючы кліку-кандыдата, можна за палінаміяльны час праверыць, ці сапраўды гэта кліка патрэбнага памеру. Праблема клікі таксама NP-поўная, што азначае, што яе эфектыўнае рашэнне будзе азначаць, што ўсе праблемы NP могуць быць вырашаны эфектыўна.
Вывучэнне P супраць NP і NP-паўнаты прывяло да распрацоўкі розных метадаў і інструментаў у тэарэтычнай інфарматыцы. Адным з такіх метадаў з'яўляецца канцэпцыя паліномнага скарачэння часу, якая выкарыстоўваецца, каб паказаць, што адна праблема, па меншай меры, такая ж складаная, як іншая. Скарачэнне паліномнага часу ад задачы A да праблемы B - гэта пераўтварэнне, якое пераўтварае асобнікі A ў асобнікі B за палінаміяльны час, так што рашэнне трансфармаванага асобніка B можа быць выкарыстана для вырашэння зыходнага асобніка A. Калі праблема A можа быць зведзена да задачы B за палінаміяльны час, а B можа быць вырашана за палінаміяльны час, тады A таксама можа быць вырашана за палінаміяльны час.
Яшчэ адна важная канцэпцыя - гэта паняцце алгарытмаў апраксімацыі, якія забяспечваюць амаль аптымальныя рашэнні NP-цяжкіх задач (задач, якія, па меншай меры, такія ж складаныя, як NP-поўныя задачы) за паліномны час. Нягледзячы на тое, што гэтыя алгарытмы не абавязкова знаходзяць дакладнае аптымальнае рашэнне, яны прапануюць практычны падыход да вырашэння цяжкавырашальных праблем, прапаноўваючы рашэнні, блізкія да найлепшых. Напрыклад, задача каміваяжора мае добра вядомы алгарытм апраксімацыі, які гарантуе тур з каэфіцыентам 1.5 аптымальнага тура для метрыкі TSP (дзе адлегласці задавальняюць няроўнасці трохвугольніка).
Наступствы вырашэння пытання P супраць NP выходзяць за рамкі тэарэтычнай інфарматыкі. У крыптаграфіі многія схемы шыфравання абапіраюцца на цвёрдасць пэўных праблем, такіх як разкладка на цэлыя множнікі і дыскрэтныя лагарыфмы, якія, як мяркуюць, знаходзяцца ў NP, але не ў P. Калі б P было роўна NP, гэтыя праблемы патэнцыйна маглі б быць вырашаны эфектыўна, ставячы пад пагрозу бяспека крыптаграфічных сістэм. І наадварот, доказ P ≠ NP забяспечыў бы больш трывалую аснову для бяспекі такіх сістэм.
Пры аптымізацыі многія праблемы рэальнага свету, такія як планаванне, маршрутызацыя і размеркаванне рэсурсаў, мадэлююцца як NP-цвёрдыя праблемы. Калі б P было роўна NP, гэта азначала б, што можна было б распрацаваць эфектыўныя алгарытмы для аптымальнага вырашэння гэтых праблем, што прывяло б да значнага прагрэсу ў розных галінах. Аднак цяперашняе дапушчэнне, што P ≠ NP, прывяло да распрацоўкі эўрыстычных і набліжаных алгарытмаў, якія забяспечваюць практычныя рашэнні гэтых праблем.
Пытанне P супраць NP таксама мае філасофскае значэнне, паколькі закранае прыроду матэматычнай ісціны і межы чалавечых ведаў. Калі б P было роўна NP, гэта азначала б, што кожнае матэматычнае сцвярджэнне з кароткім доказам можа быць эфектыўна знойдзена, патэнцыйна змяніўшы працэс матэматычных адкрыццяў. З іншага боку, калі P ≠ NP, гэта сведчыць аб тым, што існуюць неад'емныя межы таго, што можна эфектыўна вылічыць і праверыць, што падкрэслівае складанасць і багацце матэматычных структур.
Нягледзячы на адсутнасць канчатковага адказу на пытанне P супраць NP, даследаванні, звязаныя з ім, прывялі да больш глыбокага разумення вылічальнай складанасці і распрацоўкі шматлікіх метадаў і інструментаў, якія аказалі глыбокі ўплыў на інфарматыку. Імкненне да вырашэння гэтага пытання працягвае натхняць і кідаць выклік даследчыкам, спрыяючы прагрэсу ў гэтай галіне і пашыраючы наша разуменне фундаментальных межаў вылічэнняў.
Іншыя апошнія пытанні і адказы адносна складанасць:
- Клас PSPACE не роўны класу EXPSPACE?
- Ці з'яўляецца клас складанасці P падмноствам класа PSPACE?
- Ці можам мы даказаць, што класы Np і P аднолькавыя, знайшоўшы эфектыўнае паліномнае рашэнне для любой поўнай задачы NP на дэтэрмінаванай TM?
- Ці можа клас NP быць роўны класу EXPTIME?
- Ці ёсць у PSPACE праблемы, для якіх не вядомы алгарытм NP?
- Ці можа праблема SAT быць поўнай праблемай NP?
- Ці можа праблема знаходзіцца ў класе складанасці NP, калі існуе недэтэрмінаваная машына Цьюрынга, якая вырашыць яе за паліномны час
- NP - гэта клас моў, якія маюць паліномныя праверкі часу
- Ці кожная кантэкстна-свабодная мова ў класе складанасці P?
- Ці існуе супярэчнасць паміж вызначэннем NP як класа задач рашэння з праверкамі паліномнага часу і тым фактам, што задачы ў класе P таксама маюць праверкі паліномнага часу?
Больш пытанняў і адказаў глядзіце ў Complexity