Пытанне "Ці можа задача быць у класе складанасці NP, калі існуе недэтэрмінаваная машына Цьюрынга, якая вырашыць яе за паліномны час?" закранае асноўныя паняцці тэорыі складанасці вылічэнняў. Каб вырашыць гэтае пытанне комплексна, мы павінны разгледзець азначэнні і характарыстыкі класа складанасці NP і ролю недэтэрмінаваных машын Цьюрынга (NDTM).
Вызначэнне НП
Клас NP (недэтэрмінаваны паліномны час) складаецца з праблем прыняцця рашэнняў, для якіх дадзенае рашэнне можа быць праверана як правільнае або няправільнае ў палінамінальны час з дапамогай дэтэрмінаванай машыны Цьюрынга (DTM). Фармальна праблема прыняцця рашэння знаходзіцца ў NP, калі існуе алгарытм паліномнай праверкі часу, які можа праверыць правільнасць дадзенага сертыфіката (або сведкі) для асобніка праблемы.
Недэтэрмінаваныя машыны Цьюрынга
Недэтэрмінаваная машына Цьюрынга - гэта тэарэтычная мадэль вылічэнняў, якая пашырае магчымасці дэтэрмінаванай машыны Ц'юрынга. У адрозненне ад DTM, які прытрымліваецца аднаго вылічальнага шляху, вызначанага яго функцыяй пераходу, NDTM можа выконваць некалькі вылічальных шляхоў адначасова. На кожным кроку NDTM можа "выбіраць" з набору магчымых пераходаў, эфектыўна даследуючы мноства магчымых вылічэнняў паралельна.
Развязальнасць палінома з дапамогай NDTM
Кажуць, што праблема можа быць вырашана з дапамогай NDTM за паліномны час, калі існуе недэтэрмінаваны алгарытм, які можа знайсці рашэнне задачы за шэраг крокаў, палінамінальны па памеры ўваходных дадзеных. Гэта азначае, што для любога асобніка задачы NDTM можа даследаваць вылічальны шлях, які вядзе да рашэння за паліномны час.
Адносіны паміж NP і NDTM
Клас NP можа быць эквівалентна вызначаны ў тэрмінах NDTM. У прыватнасці, праблема рашэння знаходзіцца ў NP тады і толькі тады, калі існуе NDTM, які можа вырашыць праблему за паліномны час. Гэтая эквівалентнасць узнікае з-за таго, што NDTM можа адгадаць сертыфікат недэтэрмінаваным спосабам, а затым праверыць яго дэтэрмінаваным чынам за паліномны час.
Каб праілюстраваць гэта на прыкладзе, разгледзім добра вядомую праблему NP-поўнасці, праблему лагічнай выканальнасці (SAT). Улічваючы лагічную формулу ў кан'юнктыўнай нармальнай форме (CNF), задача складаецца ў тым, каб вызначыць, ці існуе прысваенне праўдзівых значэнняў зменным, якое робіць формулу праўдзівай. NDTM можа вырашаць SAT за паліномны час, недэтэрмінавана адгадваючы прызначэнне праўдзівых значэнняў і затым дэтэрмінавана правяраючы, ці задавальняе прызначэнне формуле. Этап праверкі, які ўключае ацэнку формулы ў адпаведнасці з угаданым прызначэннем, можа быць выкананы за паліномны час.
Наступствы развязальнасці палінома з дапамогай NDTM
Улічваючы прыведзеныя вышэй азначэнні і эквівалентнасць паміж NP і развязальнасць за паліномны час з дапамогай NDTM, мы можам зрабіць выснову, што калі існуе NDTM, які вырашае праблему за палінаміальны час, то праблема сапраўды знаходзіцца ў NP. Гэта адбываецца таму, што існаванне такога NDTM азначае, што для праблемы існуе паліномны алгарытм праверкі. Фаза недэтэрмінаванай здагадкі NDTM адпавядае генерацыі сертыфіката, а фаза дэтэрмінаванай праверкі адпавядае алгарытму паліномнай праверкі.
Далейшыя меркаванні і прыклады
Для далейшага высвятлення гэтай канцэпцыі давайце разгледзім дадатковыя прыклады праблем у NP і іх сувязь з NDTM:
1. Праблема гамільтанавага шляху: Дадзены граф, праблема Гамільтанавага шляху пытаецца, ці існуе шлях, які наведвае кожную вяршыню роўна адзін раз. NDTM можа вырашыць гэтую праблему за паліномны час шляхам недэтэрмінаванага адгадвання паслядоўнасці вяршыняў і праверкі, ці ўтварае паслядоўнасць сапраўдны гамільтанаў шлях. Этап праверкі ўключае праверку сумежнасці паслядоўных вяршыняў і забеспячэнне таго, каб кожная вяршыня была наведана роўна адзін раз, абодва з якіх можна зрабіць за паліномны час.
2. Праблема сумы падмноства: Улічваючы набор цэлых лікаў і мэтавую суму, праблема Subset Sum пытаецца, ці існуе падмноства цэлых лікаў, якое дае суму да мэты. NDTM можа вырашыць гэту праблему за паліномны час шляхам недэтэрмінаванага ўгадвання падмноства цэлых лікаў і праверкі, ці роўная сума падмноства мэты. Этап праверкі ўключае сумаванне элементаў угаданага падмноства, што можа быць зроблена за паліномны час.
3. Задача расфарбоўкі графа: Улічваючы граф і шэраг колераў, праблема афарбоўкі графа пытаецца, ці магчыма пафарбаваць вяршыні графа так, каб ніякія дзве суседнія вяршыні не мелі аднолькавы колер. NDTM можа вырашыць гэтую праблему за паліномны час шляхам недэтэрмінаванага прысваення колераў вяршыням і праверкі правільнасці афарбоўкі. Этап праверкі ўключае праверку колераў суседніх вяршыняў, што можа быць зроблена за паліномны час.
Conclusion
У святле прыведзеных азначэнняў і прыкладаў становіцца ясна, што праблема сапраўды можа быць у класе складанасці NP, калі існуе недэтэрмінаваная машына Цьюрынга, якая вырашыць яе за паліномны час. Гэтая ўзаемасувязь з'яўляецца краевугольным каменем тэорыі складанасці вылічэнняў і падкрэслівае эквівалентнасць паміж паліномнай развязальнасцю з дапамогай NDTM і прыналежнасцю да класа NP.
Іншыя апошнія пытанні і адказы адносна складанасць:
- Клас PSPACE не роўны класу EXPSPACE?
- Ці з'яўляецца клас складанасці P падмноствам класа PSPACE?
- Ці можам мы даказаць, што класы Np і P аднолькавыя, знайшоўшы эфектыўнае паліномнае рашэнне для любой поўнай задачы NP на дэтэрмінаванай TM?
- Ці можа клас NP быць роўны класу EXPTIME?
- Ці ёсць у PSPACE праблемы, для якіх не вядомы алгарытм NP?
- Ці можа праблема SAT быць поўнай праблемай NP?
- NP - гэта клас моў, якія маюць паліномныя праверкі часу
- Ці аднолькавы клас складанасці P і NP?
- Ці кожная кантэкстна-свабодная мова ў класе складанасці P?
- Ці існуе супярэчнасць паміж вызначэннем NP як класа задач рашэння з праверкамі паліномнага часу і тым фактам, што задачы ў класе P таксама маюць праверкі паліномнага часу?
Больш пытанняў і адказаў глядзіце ў Complexity