PSPACE анги нь EXPSPACE ангитай тэнцэхгүй байна уу?
PSPACE анги нь EXPSPACE ангитай тэнцүү биш үү гэсэн асуулт нь тооцооллын нарийн төвөгтэй байдлын онолын үндсэн бөгөөд шийдэгдээгүй асуудал юм. Иж бүрэн ойлголт өгөхийн тулд эдгээр нарийн төвөгтэй байдлын ангиллын тодорхойлолт, шинж чанар, үр дагавар, түүнчлэн сансрын нарийн төвөгтэй байдлын илүү өргөн хүрээг авч үзэх нь чухал юм.
Тодорхойлолт ба үндсэн шинж чанарууд
PSPACE: PSPACE анги нь олон гишүүнт орон зайг ашиглан Тьюрингийн машинаар шийдэж болох бүх шийдвэрийн бодлогоос бүрдэнэ. Албан ёсоор, хэрэв Тьюрингийн машин M болон олон гишүүнт функц p(n) байгаа бол L хэл нь PSPACE-д байдаг бөгөөд ингэснээр x оролт бүрт M машин x нь L хэлэнд байгаа эсэхийг хамгийн ихдээ p(|x|) зай ашиглан шийддэг. PSPACE нь олон гишүүнт хугацаанд (P) шийдвэрлэх боломжтой, PSPACE-д бүрэн гүйцэд хамаарах Тоо хэмжээ логикийн томьёо (QBF) бодлого зэрэг өргөн хүрээний бодлогуудыг багтаадаг.
EXPSPACE: EXPSPACE анги нь экспоненциал орон зайг ашиглан Тьюрингийн машинаар шийдэж болох шийдвэр гаргах бүх бодлогуудыг агуулдаг. Тодруулбал, хэрэв Тьюрингийн машин М болон экспоненциал функц f(n) байгаа бол L хэл нь EXPSPACE хэл дээр байх бөгөөд ингэснээр x оролт бүрт M машин x-г L хэлэнд байгаа эсэхийг хамгийн ихдээ 2^f(|x|) ашиглан шийддэг. орон зай. EXPSPACE нь PSPACE-ээс том анги бөгөөд энэ нь экспоненциалаар илүү их зай гаргах боломжийг олгож, илүү өргөн хүрээний асуудлыг шийдвэрлэх боломжийг олгодог.
PSPACE ба EXPSPACE хоорондын хамаарал
PSPACE болон EXPSPACE хоёрын хоорондын хамаарлыг ойлгохын тулд орон зайн нарийн төвөгтэй байдлын ангиллын шатлалыг таних нь чухал юм. Тодорхойлолтоор бол PSPACE нь EXPSPACE дотор агуулагддаг, учир нь олон гишүүнт орон зайг ашиглан шийдэж болох аливаа асуудлыг экспоненциал орон зайг ашиглан шийдэж болно. Албан ёсоор PSPACE ⊆ EXPSPACE. Гэсэн хэдий ч эсрэгээр нь үнэн байх албагүй; EXPSPACE нь олон гишүүнт орон зайг ашиглан шийдвэрлэх боломжгүй асуудлуудыг агуулдаг гэж өргөнөөр үздэг бөгөөд энэ нь PSPACE ≠ EXPSPACE гэсэн үг юм.
Жишээ ба үр дагавар
PSPACE бүрэн гүйцэд болох QBF асуудлыг авч үзье. Энэ асуудал нь тоон үзүүлэлттэй Булийн томьёоны үнэнийг тодорхойлоход хамаарах бөгөөд олон гишүүнт орон зайг ашиглан үүнийг шийдэж болно. QBF нь PSPACE-д бүрэн гүйцэд тул PSPACE дээрх аливаа асуудлыг олон гишүүнт хугацаанд QBF болгон бууруулж болно. Нөгөөтэйгүүр, EXPSPACE-д байгаа асуудлын жишээ нь PSPACE-д байх албагүй ч экспоненциал орон зайн хязгаартай Тьюрингийн машинуудыг ээлжлэн солиход хүрч болох асуудал юм. Энэ асуудал нь олон гишүүнт орон зайд боломжгүй олон тооны тохиргоог хянах шаардлагатай байдаг.
Сансрын шаталсан теорем
Сансар огторгуйн шаталсан теорем нь PSPACE нь EXPSPACE-д хатуу агуулагддаг гэсэн итгэл үнэмшлийн албан ёсны үндэс суурь болдог. Энэ теорем нь ямар ч орон зайгаар бүтээгдэх боломжтой f(n) функцийн хувьд f(n) орон зайд шийдэгдэх хэл байх боловч o(f(n)) орон зайд шийдэгдэхгүй гэж заасан байдаг. Энэ теоремыг f(n) = 2^n-ээр ашигласнаар бид экспоненциал орон зайд шийдвэрлэх боломжтой, олон гишүүнт орон зайг оролцуулан ямар ч дэд экспоненциал орон зайд шийдвэрлэх боломжгүй асуудлууд байгааг олж авна. Тиймээс Сансрын шатлалын теорем нь PSPACE нь EXPSPACE, өөрөөр хэлбэл PSPACE ⊂ EXPSPACE дотор хатуу агуулагддаг гэсэн үг юм.
PSPACE ≠ EXPSPACE-ийн шийдэгдээгүй мөн чанар
Сансар огторгуйн шатлалын теоремоос хүчтэй нотолгоо байгаа хэдий ч PSPACE нь EXPSPACE-тэй тэнцүү биш үү гэсэн асуулт шийдэгдээгүй хэвээр байна. Учир нь PSPACE ≠ EXPSPACE хатуу тэгш бус байдлыг нотлохын тулд EXPSPACE-д PSPACE-д шийдвэрлэх боломжгүй, өнөөг хүртэл биелээгүй байгаа тодорхой асуудал байгааг харуулах шаардлагатай болно. Хэцүү байдал нь тооцооллын нарийн төвөгтэй байдлын онолын нийтлэг сэдэв болох нарийн төвөгтэй байдлын ангиудын хоорондын ялгааг нотлох төрөлхийн сорилтод оршдог.
Илүү өргөн хүрээтэй контекст ба холбогдох нарийн төвөгтэй байдлын ангиуд
PSPACE болон EXPSPACE-ийн хоорондын харилцааг нарийн төвөгтэй байдлын ангиудын өргөн хүрээний хүрээнд контекстоор тодорхойлж болно. Жишээлбэл, P анги (олон гишүүнт хугацаанд шийдэгдэх бодлого) нь PSPACE-ийн дэд олонлог бөгөөд P ≠ PSPACE гэж өргөнөөр үздэг. Үүний нэгэн адил NP анги (тодорхой бус олон гишүүнт цаг) нь PSPACE дотор агуулагддаг бөгөөд алдартай P vs. NP асуудал нь энэ талбарт нээлттэй асуулт юм. Эдгээр ангиудын хязгаарлалтын харилцааг дараах байдлаар нэгтгэн дүгнэв.
– P ⊆ NP ⊆ PSPACE ⊆ EXPSPACE
Эдгээр ангиудаас гадна PSPACE-ийн дэд олонлогууд болох L (логарифм орон зай) ба NL (тодорхойлолтгүй логарифм орон зай) зэрэг бусад чухал орон зайн төвөгтэй байдлын ангиуд байдаг. Эдгээр ангиудын хоорондын хамаарал нь орон зайн хэрэгцээнд суурилсан тооцооллын нарийн төвөгтэй байдлын шатлалыг улам бүр харуулж байна.
PSPACE нь EXPSPACE-тэй тэнцүү биш үү гэсэн асуулт нь тооцооллын нарийн төвөгтэй байдлын онолын үндсэн бөгөөд шийдэгдээгүй асуудал юм. Сансар огторгуйн шаталсан теорем нь PSPACE нь EXPSPACE-д хатуу агуулагддаг гэдгийг баттай нотолгоо болгож байгаа ч PSPACE ≠ EXPSPACE хатуу тэгш бус байдлын албан ёсны нотолгоо нь олдохгүй хэвээр байна. Энэ асуултыг судлах нь нарийн төвөгтэй байдлын ангиудын өргөн хүрээг хамарсан байдал, тэдгээрийн хоорондын ялгааг нотлох төрөлхийн сорилтуудыг гэрэлтүүлдэг.
Сүүлийн үеийн бусад асуулт, хариулт Харьцуулалт:
- P нарийн төвөгтэй байдлын анги нь PSPACE ангийн дэд олонлог мөн үү?
- Детерминист TM дээр ямар ч NP бүрэн бодлогын үр ашигтай олон гишүүнт шийдийг олсноор Np ба P анги ижил гэдгийг баталж чадах уу?
- NP анги нь EXPTIME ангитай тэнцүү байж чадах уу?
- PSPACE-д тодорхой NP алгоритм байхгүй асуудал байна уу?
- SAT-ийн асуудал нь NP-ийн бүрэн асуудал байж болох уу?
- Хэрэв олон гишүүнт хугацаанд шийдвэрлэх тодорхой бус турингийн машин байгаа бол асуудал NP нарийн төвөгтэй байдлын ангилалд байж болох уу?
- NP нь олон гишүүнт цаг шалгагчтай хэлний анги юм
- P болон NP нь яг ижил нарийн төвөгтэй байдлын анги мөн үү?
- P төвөгтэй байдлын ангид контекстгүй хэл бүр байдаг уу?
- NP-г олон гишүүнт-цаг хугацааны шалгагчтай шийдвэрийн бодлогуудын анги гэж тодорхойлсон нь P ангиллын бодлогод олон гишүүнт-цаг хугацааны шалгагчтай байдгийн хооронд зөрчилдөөн байна уу?
Илүү олон асуулт, хариултыг Нарийн төвөгтэй байдлаас харна уу