"Хэрэв олон гишүүнт хугацаанд шийдвэрлэх тодорхой бус Тьюрингийн машин байгаа бол асуудал NP төвөгтэй байдлын ангилалд байж болох уу?" Тооцооллын нарийн төвөгтэй байдлын онолын үндсэн ойлголтуудыг хөндсөн. Энэ асуултыг цогцоор нь шийдвэрлэхийн тулд бид БЦГ-ын нарийн төвөгтэй байдлын ангийн тодорхойлолт, шинж чанарууд болон детерминистик бус Тюринг машинуудын (NDTM) үүргийг авч үзэх ёстой.
NP-ийн тодорхойлолт
NP анги (тодорхой бус олон гишүүнт хугацаа) нь өгөгдсөн шийд нь олон гишүүнт хугацааны туршид зөв эсвэл буруу гэдгийг детерминист Тюринг машинаар (DTM) баталгаажуулж болох шийдвэрийн бодлогуудаас бүрддэг. Албан ёсоор, тухайн асуудлын хувьд өгөгдсөн гэрчилгээний (эсвэл гэрч) зөв эсэхийг шалгах олон гишүүнт цагийн баталгаажуулалтын алгоритм байгаа бол шийдвэрийн асуудал нь NP-д байдаг.
Тодорхойлогч бус Тьюрингийн машинууд
Детерминист бус Тьюрингийн машин нь детерминист Тьюрингийн машины чадавхийг өргөтгөх тооцооллын онолын загвар юм. Шилжилтийн функцээр тодорхойлогдсон нэг тооцооллын замыг дагадаг DTM-ээс ялгаатай нь NDTM нь хэд хэдэн тооцооллын замыг нэгэн зэрэг гүйцэтгэж чаддаг. Алхам бүрт NDTM нь олон боломжит тооцооллыг зэрэгцүүлэн судалж, боломжит шилжилтийн багцаас "сонгож" чадна.
NDTM-ээр олон гишүүнт-цаг хугацааны уусгах чадвар
Оролтын хэмжээгээр олон гишүүнт хэд хэдэн алхамын дотор асуудлыг шийдэх шийдлийг олох боломжтой детерминистик бус алгоритм байгаа бол асуудлыг олон гишүүнт хугацааны NDTM-ээр шийдвэрлэх боломжтой гэж нэрлэдэг. Энэ нь асуудлын аль ч тохиолдлын хувьд NDTM нь олон гишүүнт цаг хугацааны шийдэлд хүргэдэг тооцооллын замыг судалж чадна гэсэн үг юм.
NP болон NDTM-ийн хоорондын харилцаа
NP ангиллыг NDTM-ийн хувьд адилтган тодорхойлж болно. Тодруулбал, олон гишүүнт хугацаанд асуудлыг шийдэж чадах NDTM байгаа тохиолдолд шийдвэрийн бодлого нь NP-д байдаг. Энэхүү тэнцэл нь NDTM нь гэрчилгээг тодорхой бус байдлаар тааж, дараа нь олон гишүүнт хугацааны туршид детерминистик байдлаар баталгаажуулж чаддагаас үүсдэг.
Үүнийг жишээгээр харуулахын тулд сайн мэддэг NP-бүрэн бодлого болох Boolean satisfiability problem (SAT)-ийг авч үзье. Коньюнктив хэвийн хэлбэрээр (CNF) Булийн томьёо өгөгдсөн бол томьёог үнэн болгож буй хувьсагчид үнэний утгын хуваарилалт байгаа эсэхийг тодорхойлох даалгавар юм. NDTM нь SAT-г олон гишүүнт хугацаанд шийдэж, үнэний утгуудын оноолтыг тодорхой бус аргаар тааж, дараа нь даалгавар нь томьёог хангаж байгаа эсэхийг тодорхойлох боломжтой. Таамагласан даалгаврын дагуу томьёог үнэлэхийг багтаасан баталгаажуулах алхамыг олон гишүүнт хугацаанд хийж болно.
NDTM-ээр олон гишүүнт цаг хугацааны уусгах чадварын үр дагавар
Дээрх тодорхойлолтууд болон NDTM-ээр олон гишүүнт-цаг хугацааны шийдвэрлэх чадвар ба NDTM-ийн хоорондох тэнцүү байдлыг харгалзан үзвэл, хэрэв олон гишүүнт хугацаанд асуудлыг шийддэг NDTM байгаа бол асуудал үнэхээр NP-д байна гэж дүгнэж болно. Учир нь ийм NDTM байгаа нь тухайн асуудалд олон гишүүнт цаг хугацааны баталгаажуулалтын алгоритм байгааг илтгэнэ. NDTM-ийн детерминистик бус таах үе шат нь гэрчилгээ үүсгэхтэй, харин детерминистик баталгаажуулалтын үе шат нь олон гишүүнт цаг хугацааны баталгаажуулалтын алгоритмтай тохирч байна.
Цаашид анхаарах зүйлс ба жишээнүүд
Энэхүү үзэл баримтлалыг илүү тодруулахын тулд БЦГ-ын асуудлууд болон тэдгээрийн NDTM-тэй харилцах харилцааны нэмэлт жишээг авч үзье.
1. Гамильтоны замын асуудал: График өгвөл Гамильтоны замын бодлого нь орой бүр дээр яг нэг удаа очдог зам байгаа эсэхийг асууна. NDTM нь оройнуудын дарааллыг тодорхойгүй байдлаар таамаглаж, дараа нь зөв Гамильтоны замыг үүсгэж байгаа эсэхийг шалгах замаар олон гишүүнт хугацаанд энэ асуудлыг шийдэж чадна. Баталгаажуулах алхам нь дараалсан оройнуудын зэргэлдээ байдлыг шалгаж, орой тус бүрд яг нэг удаа очсон эсэхийг шалгах явдал бөгөөд аль алиныг нь олон гишүүнт цагт хийж болно.
2. Дэд олонлогийн нийлбэрийн асуудал: Бүхэл тоонуудын багц ба зорилтот нийлбэр өгөгдсөн бол Дэд олонлогийн нийлбэрийн асуудал нь зорилтод хүрэх бүхэл тоонуудын дэд олонлог байгаа эсэхийг асууна. NDTM нь бүхэл тоонуудын дэд олонлогийг тодорхойгүй таах замаар энэ асуудлыг олон гишүүнт хугацаанд шийдэж, дараа нь дэд олонлогийн нийлбэр зорилтот хэмжээтэй тэнцүү эсэхийг шалгах боломжтой. Баталгаажуулах алхам нь таасан дэд олонлогийн элементүүдийг нэгтгэн дүгнэх явдал бөгөөд үүнийг олон гишүүнт хугацаанд хийж болно.
3. График будах асуудал: График болон хэд хэдэн өнгө өгөгдсөн бол График будах бодлого нь графын оройг хоёр зэргэлдээх орой нь ижил өнгөтэй байхаар өнгөөр будаж болох эсэхийг асууна. NDTM нь оройн цэгүүдэд өнгийг тодорхой бус байдлаар хуваарилж, дараа нь будалт хүчинтэй эсэхийг шалгах замаар олон гишүүнт цагийн энэ асуудлыг шийдэж чадна. Баталгаажуулах алхам нь зэргэлдээх оройнуудын өнгийг шалгах явдал бөгөөд үүнийг олон гишүүнт хугацаанд хийж болно.
Дүгнэлт
Өгөгдсөн тодорхойлолтууд болон жишээнүүдээс харахад олон гишүүнт хугацаанд шийдвэрлэх тодорхой бус Тьюрингийн машин байгаа тохиолдолд асуудал үнэхээр NP нарийн төвөгтэй байдлын ангилалд багтах нь тодорхой байна. Энэ хамаарал нь тооцооллын нарийн төвөгтэй байдлын онолын тулгын чулуу бөгөөд NDTM-ээр олон гишүүнт-цаг хугацааны уусгах чадвар болон NP ангиллын гишүүнчлэлийн хоорондох тэнцүү байдлыг онцолж өгдөг.
Сүүлийн үеийн бусад асуулт, хариулт Харьцуулалт:
- PSPACE анги нь EXPSPACE ангитай тэнцэхгүй байна уу?
- P нарийн төвөгтэй байдлын анги нь PSPACE ангийн дэд олонлог мөн үү?
- Детерминист TM дээр ямар ч NP бүрэн бодлогын үр ашигтай олон гишүүнт шийдийг олсноор Np ба P анги ижил гэдгийг баталж чадах уу?
- NP анги нь EXPTIME ангитай тэнцүү байж чадах уу?
- PSPACE-д тодорхой NP алгоритм байхгүй асуудал байна уу?
- SAT-ийн асуудал нь NP-ийн бүрэн асуудал байж болох уу?
- NP нь олон гишүүнт цаг шалгагчтай хэлний анги юм
- P болон NP нь яг ижил нарийн төвөгтэй байдлын анги мөн үү?
- P төвөгтэй байдлын ангид контекстгүй хэл бүр байдаг уу?
- NP-г олон гишүүнт-цаг хугацааны шалгагчтай шийдвэрийн бодлогуудын анги гэж тодорхойлсон нь P ангиллын бодлогод олон гишүүнт-цаг хугацааны шалгагчтай байдгийн хооронд зөрчилдөөн байна уу?
Илүү олон асуулт, хариултыг Нарийн төвөгтэй байдлаас харна уу