Олон гишүүнт цаг хугацааны шалгагчийг олон гишүүнт цаг хугацааны детерминистик бус Тьюрингийн машинаас бүтээх үйл явцыг тайлбарла.
Олон гишүүнт цаг шалгагчийг олон гишүүнт цаг хугацааны детерминистик бус Тьюрингийн машинаас (NTM) системчилсэн процессыг дагаж байгуулж болно. Энэ үйл явцыг ойлгохын тулд нарийн төвөгтэй байдлын онолын тухай ойлголтууд, ялангуяа P ба NP ангиуд, олон гишүүнт баталгаажуулалтын тухай ойлголтын талаар тодорхой ойлголттой байх шаардлагатай.
Тооцооллын нарийн төвөгтэй байдлын онолд Р нь олон гишүүнт цаг хугацаанд детерминист Тьюрингийн машинаар шийдэж болох шийдвэрийн бодлогын ангиллыг хэлнэ. Нөгөөтэйгүүр, NP гэдэг нь шийдлийг олон гишүүнт хугацааны туршид детерминист Тьюрингийн машинаар шалгаж болох шийдвэрийн асуудлын ангиллыг хэлнэ. Эдгээр хоёр ангиллын гол ялгаа нь P нь үр дүнтэй шийдвэрлэх боломжтой асуудлуудыг илэрхийлдэг бол NP нь үр дүнтэй шалгаж болох асуудлуудыг илэрхийлдэг.
Олон гишүүнт цаг шалгагч нь олон гишүүнт цаг хугацааны NP асуудлын шийдлийн зөв эсэхийг шалгах боломжтой детерминист Тьюрингийн машин юм. Олон гишүүнт хугацааны NTM-ээс ийм баталгаажуулагчийг бүтээх үйл явц нь дараах алхмуудыг агуулна.
1. NP бодлого өгөгдсөн бол X бодлого гэж бодъё, бид X-ийг шийдэж чадах NTM M олон гишүүнт цаг байгаа гэж үзье. Энэхүү NTM M нь тооцооллын хэд хэдэн салбартай бөгөөд тус бүр нь өөр боломжит гүйцэтгэлийн замыг төлөөлдөг.
2. Бид NTM M-ийн зан төлөвийг загварчлах замаар X асуудлын хувьд олон гишүүнт цаг хугацааны шалгагч V-г бүтээдэг. V шалгагч нь X асуудлын шийдэл болон гэрчилгээ гэсэн хоёр оролтыг авдаг. Гэрчилгээ нь зөв шийдэл гэдгийг батлах баталгаа юм.
3. Баталгаажуулагч V эхлээд гэрчилгээ нь хүчинтэй форматтай эсэхийг шалгана. Баталгаажуулагч нь гэрчилгээний хүлээгдэж буй бүтцийг мэддэг тул энэ алхамыг олон гишүүнт хугацаанд хийж болно.
4. Дараа нь V шалгагч нь өгөгдсөн шийдэл болон сертификат дээрх NTM M-ийн үйлдлийг дуурайлган хийдэг. Энэ нь M-ийн тооцооллын бүх боломжит салбаруудыг гүйцэтгэдэг бөгөөд аль нэг салбар нь оролтыг хүлээн авч байгаа эсэхийг шалгадаг. NTM M олон гишүүнт хугацаанд ажилладаг тул энэ симуляцийг олон гишүүнт хугацаанд хийж болно.
5. Хэрэв V шалгагч нь хамгийн багадаа нэг хүлээн авагч тооцооллын салбарыг олсон бол оролтыг хүлээн авна. Энэ нь шийдэл нь X асуудлын зөв эсэхийг баталгаажуулсан гэсэн үг юм. Үгүй бол аль ч салбар хүлээж авахгүй бол шалгагч оролтоос татгалзана.
Олон гишүүнт цаг шалгагчийг бүтээх гол санаа нь NTM M нь олон гишүүнт цаг хугацааны зөв гэрчилгээг тааж чадна гэсэн үг юм. M-ийн зан төлөвийг дуурайж, боломжит бүх салбарыг шалгаснаар V шалгагч нь шийдлийн зөв эсэхийг үр дүнтэй шалгаж чадна.
Энэ үйл явцыг харуулахын тулд жишээ татъя. Өгөгдсөн график нь NP-бүрэн бодлого болох Гамильтоны мөчлөгтэй эсэхийг тодорхойлох асуудлыг авч үзье. Энэ асуудлыг шийдэж чадах NTM M олон гишүүнт цаг байгаа гэж бид таамаглаж байна.
Энэ асуудлын олон гишүүнт цаг хугацааны баталгаажуулагч V байгуулахын тулд бид өгөгдсөн график болон сертификат дээрх M-ийн үйлдлийг дуурайлган хийдэг. Баталгаажуулагч нь тухайн гэрчилгээ нь орой тус бүр дээр яг нэг удаа очиж, мөчлөг үүсгэж байгааг баталгаажуулах замаар хүчинтэй Гамильтоны мөчлөгийг илэрхийлж байгаа эсэхийг шалгадаг.
М-ийн тооцооллын бүх боломжит салбаруудыг бүрэн загварчлах замаар шалгагч нь өгөгдсөн график Гамильтоны мөчлөгтэй эсэхийг үр дүнтэй тодорхойлж чадна. Хэрэв M-ийн дор хаяж нэг салбар оролтыг хүлээн авбал шалгагч нь оролтыг хүчинтэй Гамильтоны мөчлөг гэж хүлээн авна. Үгүй бол энэ нь оролтоос татгалздаг.
Олон гишүүнт цаг NTM-ээс олон гишүүнт цаг шалгагчийг бүтээх нь NTM-ийн зан төлөвийг загварчлах, тооцооллын бүх боломжит салбаруудыг шалгах явдал юм. Энэ процесс нь БЦГ-ын асуудлыг шийдэх шийдлүүдийг үр дүнтэй шалгах боломжийг олгодог. Ийм шалгагчийг байгуулснаар бид асуудлыг олон гишүүнт цаг хугацаанд шалгах чадварт нь үндэслэн ангилж болно.
Сүүлийн үеийн бусад асуулт, хариулт Харьцуулалт:
- PSPACE анги нь EXPSPACE ангитай тэнцэхгүй байна уу?
- P нарийн төвөгтэй байдлын анги нь PSPACE ангийн дэд олонлог мөн үү?
- Детерминист TM дээр ямар ч NP бүрэн бодлогын үр ашигтай олон гишүүнт шийдийг олсноор Np ба P анги ижил гэдгийг баталж чадах уу?
- NP анги нь EXPTIME ангитай тэнцүү байж чадах уу?
- PSPACE-д тодорхой NP алгоритм байхгүй асуудал байна уу?
- SAT-ийн асуудал нь NP-ийн бүрэн асуудал байж болох уу?
- Хэрэв олон гишүүнт хугацаанд шийдвэрлэх тодорхой бус турингийн машин байгаа бол асуудал NP нарийн төвөгтэй байдлын ангилалд байж болох уу?
- NP нь олон гишүүнт цаг шалгагчтай хэлний анги юм
- P болон NP нь яг ижил нарийн төвөгтэй байдлын анги мөн үү?
- P төвөгтэй байдлын ангид контекстгүй хэл бүр байдаг уу?
Илүү олон асуулт, хариултыг Нарийн төвөгтэй байдлаас харна уу