Контекст мэдрэмтгий хэлүүдийг Тьюрингийн машин таних боломжтой юу?

Контекст мэдрэмтгий хэлүүд (CSLs) нь контекст мэдрэмтгий дүрмээр тодорхойлогддог албан ёсны хэлний анги юм. Эдгээр дүрмүүд нь контекстээс ангид дүрмийн ерөнхий дүрмүүд бөгөөд солих нь тодорхой нөхцөл байдалд тохиолдсон тохиолдолд мөрийг өөр тэмдэгт мөрөөр орлуулах үйлдвэрлэлийн дүрмийг зөвшөөрдөг. Энэ ангиллын хэл нь тооцооллын онолд чухал ач холбогдолтой тул илүү их байдаг

Доор тэмдэглэгдсэн: , , , , ,

PSPACE анги нь EXPSPACE ангитай тэнцэхгүй байна уу?

PSPACE анги нь EXPSPACE ангитай тэнцүү биш үү гэсэн асуулт нь тооцооллын нарийн төвөгтэй байдлын онолын үндсэн бөгөөд шийдэгдээгүй асуудал юм. Иж бүрэн ойлголт өгөхийн тулд эдгээр нарийн төвөгтэй байдлын ангиллын тодорхойлолт, шинж чанар, үр дагавар, түүнчлэн сансрын нарийн төвөгтэй байдлын илүү өргөн хүрээг авч үзэх нь чухал юм. Тодорхойлолт ба үндсэн

Доор тэмдэглэгдсэн: , , , , ,

P нарийн төвөгтэй байдлын анги нь PSPACE ангийн дэд олонлог мөн үү?

Тооцооллын нарийн төвөгтэй байдлын онолын чиглэлээр P болон PSPACE нарийн төвөгтэй байдлын ангиудын хоорондын хамаарал нь судалгааны үндсэн сэдэв юм. P нарийн төвөгтэй байдлын анги нь PSPACE ангиллын дэд олонлог уу, эсвэл хоёр анги ижил байна уу гэсэн асуултыг шийдвэрлэхийн тулд тодорхойлолт, шинж чанарыг анхаарч үзэх хэрэгтэй.

Доор тэмдэглэгдсэн: , , , , ,

PSPACE-д тодорхой NP алгоритм байхгүй асуудал байна уу?

Тооцооллын нарийн төвөгтэй байдлын онолын хүрээнд, ялангуяа сансрын нарийн төвөгтэй байдлын ангиллыг судлахад PSPACE болон NP хоорондын хамаарал ихээхэн сонирхол татдаг. Асуултыг шууд шийдвэрлэхийн тулд: тийм ээ, PSPACE-д тодорхой NP алгоритм байхгүй асуудлууд байгаа. Энэхүү батламж нь эдгээр нарийн төвөгтэй байдлын ангиудын тодорхойлолт, харилцаанд үндэслэсэн болно.

Доор тэмдэглэгдсэн: , , , , ,