NP - гэта клас моў, якія маюць паліномныя праверкі часу
Клас NP, які расшыфроўваецца як "недэтэрмінаваны паліномны час", з'яўляецца фундаментальным паняццем у тэорыі складанасці вылічэнняў, падполле тэарэтычнай інфарматыкі. Каб зразумець NP, трэба спачатку зразумець паняцце задач рашэння, якія ўяўляюць сабой пытанні з адказам "так" ці "не". Мова ў гэтым кантэксце адносіцца да набору радкоў над некаторым алфавітам, дзе кожны радок кадуе асобнік праблемы рашэння.
Кажуць, што мова (L) знаходзіцца ў NP, калі для (L) існуе верыфікатар паліномнага часу. Верыфікатар - гэта дэтэрмінаваны алгарытм (V), які прымае два ўваходныя дадзеныя: асобнік (x) і сертыфікат (y). Сертыфікат (y) таксама вядомы як «сведка» або «доказ». Верыфікатар (V) правярае, ці пацвярджае сертыфікат (y) прыналежнасць (x) да мовы (L). Фармальна мова (L) знаходзіцца ў NP, калі існуе алгарытм паліномнага часу (V) і паліном (p(n)), такія што для кожнага радка (x у L) існуе радок (y) з ( |y|. leq p(|x|)) і (V(x, y) = 1). І наадварот, для кожнага радка (x, акрамя L) не існуе такога радка (y), што (V(x, y) = 1).
Каб растлумачыць гэтую канцэпцыю, разгледзім добра вядомую праблему "булева выканальнасці" (SAT). Праблема SAT пытаецца, ці існуе прысваенне значэнняў праўдзівасці зменным у дадзенай лагічнай формуле так, што формула ацэньваецца як праўдзівая. Праблема SAT знаходзіцца ў NP, таму што, улічваючы лагічную формулу ( phi ) і прысваенне ( alpha ) праўдзівых значэнняў яе зменным, можна за палінаміяльны час праверыць, ці ( alpha ) задавальняе ( phi ). Тут асобнік ( x ) - гэта лагічная формула ( phi ), а сертыфікат ( y ) - гэта прызначэнне ( alpha ). Верыфікатар (V) правярае, ці адпавядае (альфа) (фі) сапраўднасці, што можна зрабіць за паліномны час адносна памеру (фі).
Яшчэ адзін паказальны прыклад - задача «Гамільтанаў шлях». Гэтая задача пытаецца, ці існуе шлях у дадзеным графе, які наведвае кожную вяршыню роўна адзін раз. Праблема гамільтанавага шляху таксама ўваходзіць у NP, таму што, маючы граф (G) і паслядоўнасць вяршыняў (P), можна праверыць за паліномны час, ці з'яўляецца (P) гамільтанавым шляхам у (G). У гэтым выпадку асобнік ( x ) — гэта граф ( G ), а сертыфікат ( y ) — паслядоўнасць вяршыняў ( P ). Верыфікатар ( V ) правярае, ці ўтварае ( P ) гамільтанаў шлях, што можна зрабіць за паліномны час адносна памеру ( G ).
Канцэпцыя магчымасці праверкі палінома з часам важная, таму што яна забяспечвае спосаб ахарактарызаваць праблемы, якія можна эфектыўна праверыць, нават калі знайсці рашэнне можа быць немагчыма з пункту гледжання вылічэнняў. Гэта прыводзіць да знакамітага пытання аб тым, ці ( P = NP ), якое пытаецца, ці кожная задача, рашэнне якой можа быць праверана за палінаміяльны час, таксама можа быць вырашана за палінаміяльны час. Клас (P) складаецца з задач рашэння, якія могуць быць вырашаны за паліномны час дэтэрмінаванай машынай Цьюрынга. Калі ( P = NP ), гэта будзе азначаць, што кожная задача з верыфікатарам паліномнага часу таксама мае вырашальнік паліномнага часу. Гэтае пытанне застаецца адной з найважнейшых адкрытых праблем інфарматыкі.
Адной з ключавых уласцівасцей NP з'яўляецца тое, што ён замкнёны адносна рэдукцый паліномнага часу. Паліномнае скарачэнне часу ад мовы ( L_1 ) да мовы ( L_2 ) — гэта функцыя, вылічальная за паліномны час ( f ), такая што ( x у L_1 ) тады і толькі тады, калі ( f(x) у L_2 ). Калі існуе паліномнае скарачэнне часу ад (L_1) да (L_2) і (L_2) знаходзіцца ў NP, то (L_1) таксама знаходзіцца ў NP. Гэта ўласцівасць важная ў вывучэнні NP-паўнаты, якая вызначае "самыя складаныя" праблемы ў NP. Задача з'яўляецца NP-поўнай, калі яна знаходзіцца ў NP і кожная задача ў NP можа быць зведзена да яе за паліномны час. Задача SAT была першай праблемай, якая даказала сваю NP-поўнасць, і яна служыць асновай для доказу NP-поўнасці іншых задач.
Каб яшчэ больш праілюстраваць канцэпцыю магчымасці праверкі палінома, разгледзім праблему "Сума падмноства". У гэтай задачы пытаецца, ці існуе падмноства дадзенага набору цэлых лікаў, сума якога дае вызначанае мэтавае значэнне. Праблема сумы падмноства знаходзіцца ў NP, таму што, маючы набор цэлых лікаў ( S ), мэтавае значэнне ( t ) і падмноства ( S' ) з ( S ), можна за палінаміяльны час праверыць, ці сума элементаў у (S') роўна (t). Тут асобнік ( x ) — гэта пара ( (S, t) ), а сертыфікат ( y ) — падмноства ( S' ). Верыфікатар ( V ) правярае, ці роўная сума элементаў у ( S' ) ( t ), што можна зрабіць за паліномны час адносна памеру ( S ).
Важнасць паліномнай праверкі часу выходзіць за рамкі тэарэтычных меркаванняў. Практычна гэта азначае, што для праблем у NP, калі прапанаванае рашэнне (сертыфікат) прадастаўляецца, яго можна эфектыўна праверыць. Гэта мае значныя наступствы для крыптаграфічных пратаколаў, праблем аптымізацыі і розных абласцей, дзе важная праверка правільнасці рашэння.
Падводзячы вынік, клас NP ахоплівае задачы рашэння, для якіх прапанаванае рашэнне можа быць праверана за палінаміальны час з дапамогай дэтэрмінаванага алгарытму. Гэтая канцэпцыя з'яўляецца асноватворнай у тэорыі вылічальнай складанасці і мае глыбокія наступствы як для тэарэтычных, так і для практычных аспектаў інфарматыкі. Вывучэнне NP, магчымасці праверкі палінома ў часе і звязаных з імі паняццяў, такіх як NP-паўната, па-ранейшаму застаюцца актыўнай і важнай сферай даследаванняў.
Іншыя апошнія пытанні і адказы адносна складанасць:
- Клас PSPACE не роўны класу EXPSPACE?
- Ці з'яўляецца клас складанасці P падмноствам класа PSPACE?
- Ці можам мы даказаць, што класы Np і P аднолькавыя, знайшоўшы эфектыўнае паліномнае рашэнне для любой поўнай задачы NP на дэтэрмінаванай TM?
- Ці можа клас NP быць роўны класу EXPTIME?
- Ці ёсць у PSPACE праблемы, для якіх не вядомы алгарытм NP?
- Ці можа праблема SAT быць поўнай праблемай NP?
- Ці можа праблема знаходзіцца ў класе складанасці NP, калі існуе недэтэрмінаваная машына Цьюрынга, якая вырашыць яе за паліномны час
- Ці аднолькавы клас складанасці P і NP?
- Ці кожная кантэкстна-свабодная мова ў класе складанасці P?
- Ці існуе супярэчнасць паміж вызначэннем NP як класа задач рашэння з праверкамі паліномнага часу і тым фактам, што задачы ў класе P таксама маюць праверкі паліномнага часу?
Больш пытанняў і адказаў глядзіце ў Complexity