Апішыце працэс пабудовы паліномнага праверкі часу з паліномнай недэтэрмінаванай машыны Цьюрынга.
Паліномны верыфікатар часу можа быць пабудаваны на аснове паліномнай недэтэрмінаванай машыны Цьюрынга (NTM), выконваючы сістэматычны працэс. Каб зразумець гэты працэс, вельмі важна мець дакладнае разуменне паняццяў тэорыі складанасці, у прыватнасці, класаў P і NP, а таксама паняцця паліномнай праверкі.
У тэорыі складанасці вылічэнняў P адносіцца да класа задач рашэння, якія могуць быць вырашаны дэтэрмінаванай машынай Цьюрынга за палінаміальны час. З іншага боку, NP адносіцца да класа задач рашэння, для якіх рашэнне можа быць праверана за палінаміяльны час дэтэрмінаванай машынай Цьюрынга. Ключавое адрозненне паміж гэтымі двума класамі заключаецца ў тым, што P прадстаўляе праблемы, якія можна эфектыўна вырашыць, у той час як NP прадстаўляе праблемы, якія можна эфектыўна праверыць.
Верыфікатар паліномнага часу - гэта дэтэрмінаваная машына Цьюрынга, якая можа правяраць правільнасць рашэння задачы NP за палінамінальны час. Працэс пабудовы такога верыфікатара з паліномнага часу NTM ўключае ў сябе наступныя этапы:
1. Улічваючы задачу NP, скажам, задачу X, мы мяркуем існаванне паліномнага часу NTM M, які можа вырашыць X. Гэты NTM M мае некалькі галін вылічэнняў, кожная з якіх прадстаўляе іншы магчымы шлях выканання.
2. Мы ствараем паліномны верыфікатар часу V для задачы X шляхам мадэлявання паводзін NTM M. Верыфікатар V прымае два ўваходныя дадзеныя: рашэнне задачы X і сертыфікат. Сертыфікат з'яўляецца доказам правільнасці рашэння.
3. Верыфікатар V спачатку правярае, ці мае сертыфікат сапраўдны фармат. Гэты крок можа быць выкананы за паліномны час, паколькі верыфікатар ведае чаканую структуру сертыфіката.
4. Далей верыфікатар V імітуе паводзіны NTM M на дадзеным рашэнні і сертыфікаце. Ён выконвае ўсе магчымыя галіны вылічэння M, правяраючы, ці прымае якая-небудзь галіна ўвод. Гэта мадэляванне можа быць выканана за палінаміяльны час, паколькі NTM M працуе за палінаміяльны час.
5. Калі праверка V знаходзіць хаця б адну прымальную галіну вылічэнняў, яна прымае ўвод. Гэта азначае, што рашэнне правяраецца як правільнае для праблемы X. У адваротным выпадку, калі ні адна з галін не прымае, верыфікатар адхіляе ўвод.
Ключавая ідэя пабудовы верыфікатара паліномнага часу заключаецца ў тым, што NTM M можа адгадаць правільны сертыфікат за палінамінальны час. Мадэлюючы паводзіны M і правяраючы ўсе магчымыя галіны, верыфікатар V можа эфектыўна правяраць правільнасць рашэння.
Давайце возьмем прыклад, каб праілюстраваць гэты працэс. Разгледзім праблему вызначэння таго, ці мае дадзены граф гамільтанаў цыкл, што з'яўляецца NP-поўнай задачай. Мы мяркуем існаванне паліномнага часу NTM M, які можа вырашыць гэтую праблему.
Каб пабудаваць паліномны верыфікатар часу V для гэтай задачы, мы змадэлюем паводзіны M на дадзеным графе і сертыфікаце. Верыфікатар правярае, ці ўяўляе сертыфікат сапраўдны гамільтанаў цыкл, правяраючы, што ён наведвае кожную вяршыню роўна адзін раз і ўтварае цыкл.
Вычарпальна мадэлюючы ўсе магчымыя галіны вылічэння M, праверка можа эфектыўна вызначыць, ці мае дадзены графік гамільтанаў цыкл. Калі хаця б адна галіна M прымае ўвод, верыфікатар прымае ўвод як сапраўдны гамільтанаў цыкл. У адваротным выпадку ён адхіляе ўвод.
Пабудова паліномнага верыфікатара часу з паліномнага часовага NTM прадугледжвае мадэляванне паводзін NTM і праверку ўсіх магчымых галін вылічэнняў. Гэты працэс дазваляе эфектыўна правяраць рашэнні праблем NP. Пабудаваўшы такія верификаторы, мы можам класіфікаваць задачы на аснове іх праверкі за паліномны час.
Іншыя апошнія пытанні і адказы адносна складанасць:
- Клас PSPACE не роўны класу EXPSPACE?
- Ці з'яўляецца клас складанасці P падмноствам класа PSPACE?
- Ці можам мы даказаць, што класы Np і P аднолькавыя, знайшоўшы эфектыўнае паліномнае рашэнне для любой поўнай задачы NP на дэтэрмінаванай TM?
- Ці можа клас NP быць роўны класу EXPTIME?
- Ці ёсць у PSPACE праблемы, для якіх не вядомы алгарытм NP?
- Ці можа праблема SAT быць поўнай праблемай NP?
- Ці можа праблема знаходзіцца ў класе складанасці NP, калі існуе недэтэрмінаваная машына Цьюрынга, якая вырашыць яе за паліномны час
- NP - гэта клас моў, якія маюць паліномныя праверкі часу
- Ці аднолькавы клас складанасці P і NP?
- Ці кожная кантэкстна-свабодная мова ў класе складанасці P?
Больш пытанняў і адказаў глядзіце ў Complexity