P нарийн төвөгтэй байдлын анги нь PSPACE ангийн дэд олонлог мөн үү?
Тооцооллын нарийн төвөгтэй байдлын онолын чиглэлээр P болон PSPACE нарийн төвөгтэй байдлын ангиудын хоорондын хамаарал нь судалгааны үндсэн сэдэв юм. P нарийн төвөгтэй байдлын анги нь PSPACE ангиллын дэд олонлог уу, эсвэл хоёр анги ижил байна уу гэсэн асуултыг шийдвэрлэхийн тулд эдгээр ангиудын тодорхойлолт, шинж чанарыг авч үзэх, тэдгээрийн харилцан холболтыг шинжлэх нь чухал юм.
Нарийн төвөгтэй байдлын анги P (полиномын хугацаа) нь олон гишүүнт хугацааны дотор детерминист Тьюрингийн машинаар шийдэж болох шийдвэрийн бодлогуудаас бүрддэг. Албан ёсоор, хэрвээ х тэмдэгт мөр бүрт M нь х нь L-д хамаарах эсэхийг хамгийн ихдээ p(|x|) алхмаар шийддэг тул тодорхойлогч Тьюрингийн машин M ба олон гишүүнт p(n) байгаа бол L хэл нь P хэлэнд хамаарна. Энд | x| x мөрний уртыг илэрхийлнэ. Энгийнээр хэлбэл, P хэл дээрх асуудлыг үр дүнтэй шийдэж, шаардагдах хугацаа нь оролтын хэмжээнээс илүү олон гишүүнт өсдөг.
Нөгөөтэйгүүр, PSPACE (Polynomial Space) нь олон гишүүнт орон зайг ашиглан Тьюрингийн машинаар шийдэж болох шийдвэрийн асуудлуудыг багтаадаг. Хэрэв Тьюрингийн машин M болон олон гишүүнт p(n) байгаа бол L хэл нь PSPACE-д байдаг бөгөөд x тэмдэгт бүрт M нь х нь L-д хамаарах эсэхийг хамгийн ихдээ p(|x|) зай ашиглан шийддэг. Тооцоолоход шаардагдах хугацаа нь олон гишүүнтээр хязгаарлагдахгүй гэдгийг тэмдэглэх нь зүйтэй; зөвхөн орон зай байна.
P болон PSPACE хоорондын хамаарлыг ойлгохын тулд дараахь зүйлийг анхаарч үзээрэй.
1. PSPACE-д P-г оруулах: Олон гишүүнт хугацаанд шийдэж болох аливаа асуудлыг олон гишүүнт орон зайд мөн шийдэж болно. Учир нь олон гишүүнт хугацаанд асуудлыг шийддэг детерминист Тьюрингийн машин нь хийх алхмынхаа тооноос илүү орон зайг ашиглах боломжгүй тул ихэнх олон гишүүнт орон зайд ашиглах болно. Тиймээс P нь PSPACE-ийн дэд олонлог юм. Албан ёсоор, P ⊆ PSPACE.
2. P болон PSPACE-ийн боломжит тэгш байдал: P нь PSPACE (P = PSPACE) -тай тэнцүү эсэх тухай асуулт нь тооцооллын нарийн төвөгтэй байдлын онолын томоохон нээлттэй асуудлуудын нэг юм. Хэрэв P нь PSPACE-тэй тэнцүү байсан бол энэ нь олон гишүүнт орон зайгаар шийдэж болох бүх асуудлыг олон гишүүнт хугацаанд мөн шийдэж болно гэсэн үг юм. Гэсэн хэдий ч энэ тэгш байдлыг батлах эсвэл үгүйсгэх ямар ч нотолгоо одоогоор алга байна. Ихэнх нарийн төвөгтэй байдлын онолчид P нь PSPACE (P ⊊ PSPACE) дотор хатуу агуулагддаг гэж үздэг бөгөөд энэ нь PSPACE-д P-д байхгүй асуудлууд байгаа гэсэн үг юм.
3. Жишээ ба үр дагавар: Өгөгдсөн тоон логикийн томьёо (QBF) үнэн эсэхийг тодорхойлох асуудлыг авч үзье. TQBF (True Quantified Boolean Formula) гэгддэг энэ асуудал нь каноник PSPACE-ийн бүрэн хэмжээний бодлого юм. Бодлого PSPACE-д байгаа бол PSPACE-д бүрэн бүтсэн гэсэн үг бөгөөд PSPACE дээрх бүх асуудлыг олон гишүүнт цаг хугацааны бууралтаар багасгаж болно. TQBF нь P-д байдаггүй гэж үздэг, учир нь энэ нь хувьсагчдын бүх боломжит үнэний даалгаврыг үнэлэхийг шаарддаг бөгөөд үүнийг ерөнхийдөө олон гишүүнт хугацаанд хийх боломжгүй байдаг. Гэхдээ үүнийг олон гишүүнт орон зайг ашиглан дэд томъёог рекурсив үнэлэх замаар шийдэж болно.
4. Нарийн төвөгтэй байдлын ангиллын шатлал: P болон PSPACE-ийн хоорондын хамаарлыг нарийн төвөгтэй байдлын ангиудын өргөн хүрээг хамарсан нөхцөл байдлыг авч үзвэл илүү сайн ойлгож болно. Анги NP (Нондертерминистик олон гишүүнт цаг) нь олон гишүүнт хугацаанд шийдлийг шалгаж болох шийдвэрийн бодлогоос бүрдэнэ. P ⊆ NP ⊆ PSPACE гэдгийг мэддэг. Гэсэн хэдий ч эдгээр ангиудын хоорондын яг тодорхой хамаарал (жишээлбэл, P = NP эсвэл NP = PSPACE эсэх) шийдэгдээгүй хэвээр байна.
5. Савичийн теорем: Нарийн төвөгтэй байдлын онолын чухал үр дүн бол детерминист олон гишүүнт орон зайд (NPSPACE) шийдвэрлэх боломжтой аливаа асуудлыг мөн детерминист олон гишүүнт орон зайд шийдэж болно гэж заасан Савичийн теорем юм. Албан ёсоор NPSPACE = PSPACE. Энэхүү теорем нь PSPACE ангиллын бат бөх чанарыг онцолж, тодорхой бус байдал нь орон зайн нарийн төвөгтэй байдлын хувьд нэмэлт тооцооллын хүчийг өгдөггүй гэдгийг онцлон тэмдэглэв.
6. Практик үйлдэл: P болон PSPACE хоорондын хамаарлыг ойлгох нь практик тооцоололд чухал ач холбогдолтой. P хэл дээрх асуудлуудыг үр дүнтэй шийдвэрлэх боломжтой гэж үздэг бөгөөд бодит цагийн хэрэглээнд тохиромжтой. Үүний эсрэгээр, PSPACE дахь асуудлууд нь олон гишүүнт орон зайгаар шийдэгдэх боловч экспоненциал хугацаа шаардагдах тул том оролтод ашиглах боломжгүй болгодог. Асуудал P эсвэл PSPACE-д байгаа эсэхийг тодорхойлох нь бодит ертөнцийн хэрэглээний үр ашигтай алгоритмуудыг олох боломжийг тодорхойлоход тусалдаг.
7. Судалгааны чиглэл: P vs. PSPACE асуултыг судлах нь судалгааны идэвхтэй талбар хэвээр байна. Энэ салбарын дэвшил нь тооцооллын үндсэн хязгаарыг ойлгоход ахиц дэвшил гаргахад хүргэж болзошгүй юм. Судлаачид нарийн төвөгтэй байдлын ангиудын хоорондын хамаарлын талаар ойлголттой болохын тулд хэлхээний нарийн төвөгтэй байдал, интерактив нотолгоо, алгебрийн аргууд гэх мэт янз бүрийн арга техникийг судалдаг.
Олон гишүүнт хугацаанд шийдэгдэх аливаа асуудлыг олон гишүүнт орон зайд мөн шийдэж болох тул нарийн төвөгтэй байдлын анги P нь PSPACE-ийн дэд олонлог юм. Гэсэн хэдий ч P нь PSPACE-тэй тэнцүү эсэх нь тооцооллын нарийн төвөгтэй байдлын онолд нээлттэй асуулт хэвээр байна. P нь PSPACE-д хатуу агуулагддаг гэсэн итгэл үнэмшил давамгайлж байгаа бөгөөд энэ нь PSPACE-д P-д байхгүй асуудлууд байгааг харуулж байна. Энэ харилцаа нь тооцооллын онолын болон практикийн аль алинд нь гүн гүнзгий нөлөө үзүүлж, судлаачдын үнэн мөн чанарыг ойлгохыг эрэлхийлэхэд чиглүүлдэг. тооцооллын нарийн төвөгтэй байдал.
Сүүлийн үеийн бусад асуулт, хариулт Харьцуулалт:
- PSPACE анги нь EXPSPACE ангитай тэнцэхгүй байна уу?
- Детерминист TM дээр ямар ч NP бүрэн бодлогын үр ашигтай олон гишүүнт шийдийг олсноор Np ба P анги ижил гэдгийг баталж чадах уу?
- NP анги нь EXPTIME ангитай тэнцүү байж чадах уу?
- PSPACE-д тодорхой NP алгоритм байхгүй асуудал байна уу?
- SAT-ийн асуудал нь NP-ийн бүрэн асуудал байж болох уу?
- Хэрэв олон гишүүнт хугацаанд шийдвэрлэх тодорхой бус турингийн машин байгаа бол асуудал NP нарийн төвөгтэй байдлын ангилалд байж болох уу?
- NP нь олон гишүүнт цаг шалгагчтай хэлний анги юм
- P болон NP нь яг ижил нарийн төвөгтэй байдлын анги мөн үү?
- P төвөгтэй байдлын ангид контекстгүй хэл бүр байдаг уу?
- NP-г олон гишүүнт-цаг хугацааны шалгагчтай шийдвэрийн бодлогуудын анги гэж тодорхойлсон нь P ангиллын бодлогод олон гишүүнт-цаг хугацааны шалгагчтай байдгийн хооронд зөрчилдөөн байна уу?
Илүү олон асуулт, хариултыг Нарийн төвөгтэй байдлаас харна уу