NP анги нь EXPTIME ангитай тэнцүү байж чадах уу гэсэн асуулт нь тооцооллын нарийн төвөгтэй байдлын онолын үндсэн талуудыг судалдаг. Энэхүү асуултыг цогцоор нь шийдвэрлэхийн тулд эдгээр нарийн төвөгтэй байдлын ангиллын тодорхойлолт, шинж чанар, тэдгээрийн хоорондын хамаарал, ийм тэгш байдлын үр дагаврыг ойлгох нь чухал юм.
Тодорхойлолт ба шинж чанарууд
NP (Тодорхой бус олон гишүүнт цаг):
NP анги нь өгөгдсөн шийд нь олон гишүүнт хугацааны туршид зөв эсвэл буруу гэдгийг детерминист Тьюрингийн машинаар баталгаажуулж болох шийдвэрийн бодлогуудаас бүрдэнэ. Албан ёсоор хэл ( L ) нь олон гишүүнт-цаг хугацааны шалгагч ( V ) ба олон гишүүнт ( p ) байвал NP-д байна, тэгвэл мөр бүрт ( L-д x) гэрчилгээ ( y ) ( |y|) байх болно. leq p(|x|) ) ба ( V(x, y) = 1 ).
EXPTIME (Экспоненциал хугацаа):
EXPTIME анги нь экспоненциал хугацаанд детерминист Тьюрингийн машинаар шийдэж болох шийдвэрийн бодлогуудыг агуулдаг. Албан ёсоор хэл ( L ) нь тодорхойлогч Тьюрингийн машин ( M ) ба тогтмол ( k ) байгаа бол EXPTIME-д байдаг бөгөөд ингэснээр тэмдэгт мөр болгонд ( x in L ), ( M ) цаг хугацааны хувьд ( x ) шийддэг ( O(2) ^{n^k}) ), энд ( n ) нь ( x ) урт.
NP болон EXPTIME хоорондын хамаарал
NP нь EXPTIME-тай тэнцүү байж чадах эсэхийг шинжлэхийн тулд бид эдгээр ангиудын хоорондох мэдэгдэж буй хамаарал болон ийм тэгш байдлын үр дагаврыг авч үзэх хэрэгтэй.
1. Хамгаалалт:
NP нь EXPTIME дотор агуулагддаг нь мэдэгдэж байна. Учир нь олон гишүүнт хугацаанд (NP-ийн адил) шалгаж болох аливаа асуудлыг экспоненциал хугацаанд мөн шийдэж болно. Тодруулбал, тодорхой бус олон гишүүнт цагийн алгоритмыг детерминист экспоненциал-цаг хугацааны алгоритмаар загварчилж болно. Тиймээс, ( text {NP} subseteq text {EXPTIME} ).
2. Тусгаарлах:
Нарийн төвөгтэй байдлын онолд өргөн тархсан итгэл үнэмшил нь NP нь EXPTIME-д хатуу агуулагддаг, өөрөөр хэлбэл ( text {NP} subsetneq text {EXPTIME} ). Энэхүү итгэл үнэмшил нь NP бодлого нь детерминистик экспоненциал хугацаанд шийдэгдэх бодлогоос бага ангид тооцогддог тодорхой бус олон гишүүнт хугацаанд шийдэгддэг гэсэн баримтаас үүдэлтэй юм.
NP = EXPTIME-ийн үр дагавар
Хэрэв NP нь EXPTIME-тай тэнцүү байсан бол энэ нь тооцооллын нарийн төвөгтэй байдлын талаарх бидний ойлголтод хэд хэдэн гүнзгий үр дагаварт хүргэх болно:
1. Олон гишүүнт ба экспоненциал цаг:
Тэгш байдал ( text {NP} = text {EXPTIME} ) нь экспоненциал хугацаанд шийдэж болох аливаа асуудлыг олон гишүүнт хугацаанд мөн баталгаажуулахыг санал болгоно. Энэ нь одоогийн байдлаар экспоненциал хугацаа шаардагдаж байгаа олон асуудлыг олон гишүүнт хугацаанд шалгаж (ингэснээр шийдвэрлэх боломжтой) гэсэн үг бөгөөд энэ нь нарийн төвөгтэй байдлын онолын өнөөгийн итгэл үнэмшилтэй зөрчилдөж байна.
2. Нарийн төвөгтэй байдлын ангиудын уналт:
Хэрэв NP нь EXPTIME-тай тэнцүү байсан бол энэ нь мөн хэд хэдэн нарийн төвөгтэй байдлын ангиудыг задлах болно. Жишээлбэл, энэ нь ( text{P} = text{NP}) гэсэн утгатай тул NP-бүрэн асуудлууд олон гишүүнт хугацаанд шийдэгдэх болно. Энэ нь цаашилбал ( text{P} = text{PSPACE} ) гэсэн утгатай бөгөөд олон гишүүнт шатлалын эвдрэлд хүргэж болзошгүй.
Жишээ болон бусад анхаарах зүйлс
Үр нөлөөг харуулахын тулд дараах жишээнүүдийг авч үзье.
1. SAT (сэтгэл ханамжийн асуудал):
SAT бол сайн мэддэг NP-ийн бүрэн асуудал юм. Хэрэв NP нь EXPTIME-тай тэнцүү байсан бол SAT-г детерминистик экспоненциал хугацаанд шийдэж болно гэсэн үг. Илүү чухал нь, SAT-ыг олон гишүүнт хугацаанд шалгаж, улмаар олон гишүүнт хугацаанд шийдэж, ( text{P} = text{NP}) гэсэн үг юм.
2. Шатар:
Шатрын өгөгдсөн байрлалд тоглогч ялах стратеги байгаа эсэхийг тодорхойлох асуудал EXPTIME-д байдаг. Хэрэв NP нь EXPTIME-тай тэнцүү байсан бол ийм асуудлыг олон гишүүнт хугацаанд шалгаж болно гэсэн үг бөгөөд одоогоор боломжгүй гэж үзэж байна.
Дүгнэлт
NP анги нь EXPTIME ангитай тэнцэх эсэх нь тооцооллын нарийн төвөгтэй байдлын онолд чухал ач холбогдолтой асуудал юм. Одоогийн мэдлэг дээр үндэслэн NP-г EXPTIME-д багтаасан гэж үздэг. NP нь EXPTIME-тай тэнцүү байхын үр дагавар нь гүн гүнзгий байх бөгөөд энэ нь хэд хэдэн нарийн төвөгтэй байдлын ангиудыг сүйрүүлж, олон гишүүнт ба экспоненциал цаг хугацааны талаарх бидний одоогийн ойлголтыг алдагдуулж байна.
Сүүлийн үеийн бусад асуулт, хариулт Харьцуулалт:
- PSPACE анги нь EXPSPACE ангитай тэнцэхгүй байна уу?
- P нарийн төвөгтэй байдлын анги нь PSPACE ангийн дэд олонлог мөн үү?
- Детерминист TM дээр ямар ч NP бүрэн бодлогын үр ашигтай олон гишүүнт шийдийг олсноор Np ба P анги ижил гэдгийг баталж чадах уу?
- PSPACE-д тодорхой NP алгоритм байхгүй асуудал байна уу?
- SAT-ийн асуудал нь NP-ийн бүрэн асуудал байж болох уу?
- Хэрэв олон гишүүнт хугацаанд шийдвэрлэх тодорхой бус турингийн машин байгаа бол асуудал NP нарийн төвөгтэй байдлын ангилалд байж болох уу?
- NP нь олон гишүүнт цаг шалгагчтай хэлний анги юм
- P болон NP нь яг ижил нарийн төвөгтэй байдлын анги мөн үү?
- P төвөгтэй байдлын ангид контекстгүй хэл бүр байдаг уу?
- NP-г олон гишүүнт-цаг хугацааны шалгагчтай шийдвэрийн бодлогуудын анги гэж тодорхойлсон нь P ангиллын бодлогод олон гишүүнт-цаг хугацааны шалгагчтай байдгийн хооронд зөрчилдөөн байна уу?
Илүү олон асуулт, хариултыг Нарийн төвөгтэй байдлаас харна уу