Олон гишүүнт цаг шалгагчийг хэрхэн ижил төстэй детерминистик бус Тьюрингийн машин болгон хувиргах вэ?
Олон гишүүнт цагийн шалгагчийг нотлох гэрчилгээг тааж, олон гишүүнт хугацаанд баталгаажуулах машин бүтээснээр ижил төстэй детерминистик бус Тьюрингийн машин болгон хувиргаж болно. Энэхүү хувиргалт нь детерминистик бус тооцооллын үзэл баримтлал дээр суурилдаг бөгөөд энэ нь машинд бүх боломжит замыг нэгэн зэрэг судлах боломжийг олгодог.
Энэ хөрвүүлэлтийг ойлгохын тулд эхлээд олон гишүүнт цаг шалгагч гэж юу болохыг тодорхойлъё. Тооцооллын нарийн төвөгтэй байдлын онолд олон гишүүнт цаг шалгагч нь олон гишүүнт хугацааны туршид шийдвэрийн асуудлын шийдлийн зөв эсэхийг шалгах боломжтой детерминист Тьюрингийн машин юм. Энэ нь асуудлын жишээ болон нотлох гэрчилгээ гэсэн хоёр оролтыг авч, тухайн тохиолдолд гэрчилгээ нь хүчинтэй нотлох баримт мөн эсэхийг тодорхойлдог.
Одоо олон гишүүнт цаг шалгагчийг эквивалент детерминистик бус Тьюрингийн машин болгон хөрвүүлэхийн тулд бид детерминистик бус тооцооллын шинж чанарыг авч үзэх хэрэгтэй. Детерминистик бус Тьюрингийн машинд алхам бүрт машин олон төлөвт байж, нэгэн зэрэг олон төлөвт шилжиж болно. Энэ нь машинд тооцооллын бүх боломжит замыг зэрэгцүүлэн судлах боломжийг олгодог.
Баталгаажуулагчийг хөрвүүлэхийн тулд бид нотолгооны гэрчилгээг таамаглаж, дараа нь бүх боломжит зам дээр шалгагчийг дуурайдаг тодорхойгүй Тьюрингийн машиныг бүтээж болно. Хэрэв замуудын аль нэг нь зөвшөөрвөл детерминистик бус машин хүлээн авна. Үгүй бол татгалздаг.
Үүнийг жишээгээр тайлбарлая. График будах асуудлыг шийдэх олон гишүүнт цаг шалгагч байна гэж бодъё. Баталгаажуулагч нь график болон түүний оройн өнгийг оролт болгон авч, зэргэлдээх оройнууд ижил өнгөтэй байгаа эсэхийг шалгах замаар будалт зөв эсэхийг шалгадаг.
Энэ шалгагчийг тодорхой бус Тьюрингийн машин болгон хувиргахын тулд бид будгийг таамаглаж, дараа нь бүх боломжит будгууд дээр нэгэн зэрэг шалгагчийг дуурайдаг машин бүтээдэг. Хэрэв будгийн аль нэг нь будгийн хязгаарлалтыг хангаж байвал детерминистик бус машин хүлээн авна. Үгүй бол татгалздаг.
Энэ жишээн дээр детерминистик бус машин нь оройнуудын өнгийг зэрэгцүүлэн хуваарилах замаар будгийг таамаглах болно. Дараа нь энэ нь боломжит өнгө тус бүр дээр баталгаажуулагчийг дуурайж, будалт хүчинтэй эсэхийг шалгана. Хэрэв симуляцийн аль нэг нь зөвшөөрвөл детерминистик бус машин хүлээн авна.
Энэхүү хөрвүүлэлтийг ашигласнаар олон гишүүнт цаг хугацааны шалгагчийг ижил төстэй детерминистик бус Тюринг машин болгон хувиргаж болохыг бид харж болно. Энэхүү хөрвүүлэлт нь олон гишүүнт цаг шалгагч байгаа эсэхийг харгалзан үзээд NP ангиллын бодлогын нарийн төвөгтэй байдалд дүн шинжилгээ хийх боломжийг олгодог.
Олон гишүүнт цаг хугацааны шалгагчийг нотлох гэрчилгээг тааж, бүх боломжит зам дээр нэгэн зэрэг шалгадаг машин бүтээснээр ижил төстэй детерминистик бус Тьюрингийн машин болгон хувиргаж болно. Энэхүү хувиргалт нь NP анги дахь асуудлын нарийн төвөгтэй байдлыг шинжлэх боломжийг бидэнд олгодог.
Сүүлийн үеийн бусад асуулт, хариулт Харьцуулалт:
- PSPACE анги нь EXPSPACE ангитай тэнцэхгүй байна уу?
- P нарийн төвөгтэй байдлын анги нь PSPACE ангийн дэд олонлог мөн үү?
- Детерминист TM дээр ямар ч NP бүрэн бодлогын үр ашигтай олон гишүүнт шийдийг олсноор Np ба P анги ижил гэдгийг баталж чадах уу?
- NP анги нь EXPTIME ангитай тэнцүү байж чадах уу?
- PSPACE-д тодорхой NP алгоритм байхгүй асуудал байна уу?
- SAT-ийн асуудал нь NP-ийн бүрэн асуудал байж болох уу?
- Хэрэв олон гишүүнт хугацаанд шийдвэрлэх тодорхой бус турингийн машин байгаа бол асуудал NP нарийн төвөгтэй байдлын ангилалд байж болох уу?
- NP нь олон гишүүнт цаг шалгагчтай хэлний анги юм
- P болон NP нь яг ижил нарийн төвөгтэй байдлын анги мөн үү?
- P төвөгтэй байдлын ангид контекстгүй хэл бүр байдаг уу?
Илүү олон асуулт, хариултыг Нарийн төвөгтэй байдлаас харна уу