SAT-ийн асуудал нь NP-ийн бүрэн асуудал байж болох уу?
SAT (Boolean satisfiability) бодлого нь NP-бүрэн бодлого байж чадах уу гэсэн асуулт нь тооцооллын нарийн төвөгтэй байдлын онолын үндсэн асуудал юм. Үүнийг шийдвэрлэхийн тулд NP-бүрэн байдлын тодорхойлолт, шинж чанарыг авч үзэх, SAT-ийг NP-бүрэн асуудал гэж ангилах үндэс болсон түүхэн болон онолын нөхцөл байдлыг судлах нь чухал юм.
Тодорхойлолт ба контекст
SAT асуудал: SAT асуудал нь өгөгдсөн Булийн томьёог үнэн болгодог хувьсагчдад үнэний утгын хуваарилалт байгаа эсэхийг тодорхойлох явдал юм. Булийн томьёо нь ихэвчлэн холболтын хэвийн хэлбэрээр (CNF) илэрхийлэгддэг бөгөөд томъёо нь өгүүлбэрүүдийн холболт бөгөөд заалт бүр нь шууд утгын салалт юм. Жишээлбэл, томъёо дараах байдлаар харагдаж болно.
![\[ (x_1 \lor \neg x_2) \land (\neg x_1 \lor x_3) \land (x_2 \lor \neg x_3). \]](https://eitca.org/wp-content/ql-cache/quicklatex.com-8e405df3b02de2e85a91e7957c82bb5b_l3.png "QuickLaTeX.com-ээс үзүүлсэн")
NP (Тодорхой бус олон гишүүнт цаг): Хэрэв өгөгдсөн шийд нь олон гишүүнт хугацаанд зөв эсвэл буруу гэдгийг детерминист Тьюрингийн машинаар баталгаажуулж чадвал шийдвэрийн асуудал NP-д байна. Үндсэндээ хэрэв танд нэр дэвшигчийн шийдэл байгаа бол түүний хүчинтэй эсэхийг үр дүнтэй шалгаж болно.
NP-Бүрэн: Асуудал нь хоёр нөхцлийг хангасан тохиолдолд NP-д бүрэн гүйцэд болно:
1. Энэ нь NP-д байдаг.
2. NP дахь бодлого бүрийг олон гишүүнт цаг хугацаанд нь багасгаж болно.
NP-бүрэн байдлын тухай ойлголтыг Стивен Күүк 1971 онд "Теорем батлах процедурын нийлмэл байдал" хэмээх үндсэн илтгэлдээ танилцуулж, SAT бодлого нь анхны мэдэгдэж байгаа NP-ийн бүрэн хэмжээний бодлого гэдгийг харуулсан. Энэ үр дүнг одоо Күүкийн теорем гэж нэрлэдэг.
Күүкийн теорем ба түүний үр дагавар
SAT яагаад NP-д бүрэн дүүрэн байдгийг ойлгохын тулд бид хоёр гол зүйлийг тогтоох хэрэгтэй.
1. SAT нь NP-д байдаг.
2. NP дэх бодлого бүрийг олон гишүүнт хугацааны SAT болгон бууруулж болно.
SAT нь NP дээр байна
SAT нь NP-д байгаа эсэхийг шалгахын тулд Boolean томьёо болон түүний хувьсагчид үнэний утгыг санал болгож байгаа өгөгдсөн бол бид олон гишүүнт хугацаанд томъёо үнэн гэж үнэлэгдэж байгаа эсэхийг шалгаж болно. Энэ нь заалт бүрийн дор хаяж нэг үгийн утга үнэн эсэхийг шалгахын тулд томъёоны заалт бүрийг үнэлэх явдал юм. Булийн томьёог үнэлэх нь хязгаарлагдмал тооны логик үйлдлүүдийг багтаасан энгийн процесс тул үүнийг үр дүнтэй хийх боломжтой. Тиймээс SAT нь NP-д байна, учир нь бид шийдлийг олон гишүүнт хугацаанд шалгаж болно.
Полином-Цаг хугацааны бууралт
SAT нь NP-д бүрэн гүйцэд гэдгийг нотлох хамгийн хэцүү хэсэг бол NP-ийн бүх асуудлыг олон гишүүнт хугацаанд SAT болгон бууруулж болохыг харуулах явдал юм. Энэ нь NP-ийн аливаа асуудлын хувьд тухайн асуудлын тохиолдлуудыг SAT-ын жишээ болгон хувиргадаг олон гишүүнт-цаг хугацааны тооцоологдох функц байдгийг харуулахыг хэлнэ, ингэснээр хувиргасан SAT инстанц хангагдсан тохиолдолд анхны асуудал шийдэгдэх болно.
Үүнийг харуулахын тулд ерөнхий асуудлыг авч үзье 
NP-д. Тодорхойлолтоор бол тодорхой бус олон гишүүнт цагийн Тьюрингийн машин байдаг 
энэ нь шийддэг . Машин өгөгдсөн гэрчилгээ (шийдвэр) хүчинтэй эсэхийг шалгах олон гишүүнт хугацааны баталгаажуулалтын процесстой. Бид үйлдлийг кодлох боломжтой оролт дээр 
Боловсруулсан томьёогоор томъёолсон тохиолдолд л хангагддаг хүлээж авдаг .
Кодчилол нь дараах алхмуудыг агуулна.
1. Тохиргооны кодчилол: Тохиргоог (төлөв байдал, соронзон хальсны агуулга, толгойн байрлал) кодчил Булийн хувьсагчаар. Тохиргоо бүрийг битүүдийн дарааллаар төлөөлж болно.
2. Шилжилтийн кодчилол: -ийн шилжилтийн функцийг кодчил Булийн хязгаарлалтын багц хэлбэрээр. Эдгээр хязгаарлалтууд нь тохиргооны хоорондох хүчинтэй шилжилтийг баталгаажуулдаг.
3. Анхны болон хүлээн авагч улсууд: Анхны тохиргоог (машин ажиллаж эхлэх үед) болон хүлээн авах тохиргоог (машин зогсох ба хүлээн авах үед) Булийн хязгаарлалт болгон кодчил.
-ийн зан төлөвийг агуулсан Булийн томьёог бүтээх замаар , бид хүлээн авах төлөв рүү хөтөлдөг хүчинтэй шилжилтийн дараалал байгаа тохиолдолд л хангагддаг SAT-ын жишээг үүсгэдэг. Энэ бууралтыг оролтын хэмжээтэй харьцуулахад олон гишүүнт хугацаанд хийж болно .
Жишээ нь: 3-SAT-аас SAT болгон бууруулсан
Олон гишүүнт цаг хугацааны бууралтын тухай ойлголтыг илүү тодруулахын тулд 3-SAT-ыг SAT болгон бууруулах тодорхой тохиолдлыг авч үзье. 3-SAT асуудал бол заалт бүр нь яг гурван үсэгтэй байдаг SAT-ийн онцгой тохиолдол юм. 3-SAT-ыг SAT болгон багасгахын тулд бид ямар ч 3-SAT жишээ аль хэдийн SAT-д шаардагдах хэлбэрээр (өөрөөр хэлбэл CNF томъёо) байгааг ажиглаж болно. Тиймээс бууралт нь өчүүхэн бөгөөд шугаман хугацаанд хийгдэх боломжтой бөгөөд энэ нь олон гишүүнт хугацааны бууралт юм.
SAT-ийн үр дагавар NP-бүрэн
SAT-ийг NP-complete гэж ангилах нь тооцооллын нарийн төвөгтэй байдлын онол болон практик асуудлыг шийдвэрлэхэд гүн гүнзгий нөлөө үзүүлдэг. SAT нь NP-д бүрэн хийгдсэн тул NP дээрх аливаа асуудлыг SAT жишээ болгон хөрвүүлж болно. Энэхүү түгээмэл байдал нь SAT нь бусад асуудлын нарийн төвөгтэй байдлыг тодорхойлох шалгуур болдог гэсэн үг юм. Хэрэв бид SAT-ийг шийдэх олон гишүүнт цагийн алгоритмыг олж чадвал олон гишүүнт цагийн бүх NP асуудлыг шийдэж чадна. 
.
Эсрэгээр, хэрэв бид SAT-д олон гишүүнт цагийн алгоритм байхгүй гэдгийг нотлох юм бол энэ нь гэсэн үг юм. 
. Өргөн хүрээтэй судалгаа хийсэн ч гэсэн асуулт компьютерийн шинжлэх ухааны хамгийн чухал нээлттэй асуудлын нэг хэвээр байна.
Практик хэрэглээ
Практикт SAT шийдэгчийг програм хангамжийн баталгаажуулалт, хиймэл оюун ухаан, криптограф зэрэг төрөл бүрийн салбарт өргөн ашигладаг. Орчин үеийн SAT шийдлүүд нь SAT-ийн онолын бүрэн бүтэн байдлыг үл харгалзан том, төвөгтэй тохиолдлуудыг үр дүнтэй зохицуулахын тулд нарийн алгоритм, эвристикийг ашигладаг. Эдгээр шийдэгчид урьд өмнө нь шийдэж чадахгүй байсан бодит ертөнцийн асуудлуудыг шийдвэрлэх боломжтой болгосон.
Дүгнэлт
SAT-ийн асуудал нь Күүкийн теоремоор тогтоосон NP-ийн бүрэн асуудал юм. Энэхүү ангилал нь SAT нь NP-д байдаг ба NP-ийн асуудал бүрийг олон гишүүнт цагийн SAT болгон бууруулж болдогт суурилдаг. SAT нь NP-ийн бүрэн бүтэн байдлын үр дагавар нь маш өргөн хүрээтэй бөгөөд онолын судалгаа болон компьютерийн шинжлэх ухааны практик хэрэглээнд хоёуланд нь нөлөөлдөг.
Сүүлийн үеийн бусад асуулт, хариулт Харьцуулалт:
- PSPACE анги нь EXPSPACE ангитай тэнцэхгүй байна уу?
- P нарийн төвөгтэй байдлын анги нь PSPACE ангийн дэд олонлог мөн үү?
- Детерминист TM дээр ямар ч NP бүрэн бодлогын үр ашигтай олон гишүүнт шийдийг олсноор Np ба P анги ижил гэдгийг баталж чадах уу?
- NP анги нь EXPTIME ангитай тэнцүү байж чадах уу?
- PSPACE-д тодорхой NP алгоритм байхгүй асуудал байна уу?
- Хэрэв олон гишүүнт хугацаанд шийдвэрлэх тодорхой бус турингийн машин байгаа бол асуудал NP нарийн төвөгтэй байдлын ангилалд байж болох уу?
- NP нь олон гишүүнт цаг шалгагчтай хэлний анги юм
- P болон NP нь яг ижил нарийн төвөгтэй байдлын анги мөн үү?
- P төвөгтэй байдлын ангид контекстгүй хэл бүр байдаг уу?
- NP-г олон гишүүнт-цаг хугацааны шалгагчтай шийдвэрийн бодлогуудын анги гэж тодорхойлсон нь P ангиллын бодлогод олон гишүүнт-цаг хугацааны шалгагчтай байдгийн хооронд зөрчилдөөн байна уу?
Илүү олон асуулт, хариултыг Нарийн төвөгтэй байдлаас харна уу