Компьютер яагаад зарим асуултад хэзээ ч бүрэн хариулж чаддаггүй вэ?
Өнөөдөр бид компьютерт хэт итгэдэг болсон.
Замын түгжрэлийг тооцоолж өгнө, царай танина, дуу хоолой ойлгоно, бүр хүнийг шатар, болон бусад тоглоомоор ялна. Тэгэхээр компьютер бүхнийг бодож чадна гэж бодох нь мэдээж.
Гэвч компьютерийн ухаан нэг сонин үнэнийг хэлдэг.
- Зарим асуудал угаасаа хэтэрхий хэцүү.
- Харин зарим нь бүр огт бодогдох боломжгүй.
Тэр “хэтэрхий хэцүү”-гийн яг төвд нэг домог мэт асуулт бий. Үүнийг P vs NP гэдэг.
Энгийнээр хэлбэл, асуудал шийдэхэд(бодлого бодох) хоёр өөр арга байдаг.
Бодлого бодох гэдэг нь яг юу вэ?
Хүн бодлого бодохдоо “хариуг олно” гэж ярьдаг. Харин компьютерт бол бодлого бодох гэдэг нь алгоритм гэсэн тодорхой зааврын дагуу ажиллахыг хэлнэ. Алгоритм гэдэг нь “энэ алхмыг хий, дараа нь үүнийг хий” гэсэн дараалалтай дүрэм юм. Компьютер өөрөө таамаглах, зөн совин гаргах чадваргүй. Зөвхөн заасан зүйлийг л хийдэг.
Иймээс компьютерийн ухаанд асуултыг ингэж тавьдаг:
- Ямар асуудалд ийм алгоритм бичиж болдог вэ, ямар асуудалд бичиж болдоггүй вэ?
P ангилал — компьютерийн “тайван бүс”
Зарим асуудалд алгоритм бичихэд асуудалгүй. Өгөгдөл томорсон ч бодох хугацаа нь боломжийн хэмжээнд өснө. Жишээ нь:
- Нэг хотын газрын зургаас хамгийн ойр зам олох
- Олон тооны нэрийг цагаан толгойн дарааллаар эрэмбэлэх
- Файлаас нэг үг хайх
Эдгээр асуудал нь компьютерийн хувьд “стрессгүй”. Ийм төрлийн асуудлуудыг P ангилал гэдэг. Энд “P” гэдэг нь polynomial time буюу бодох хугацаа нь зохистой өснө гэсэн утгатай.
NP ангилал — шалгах амархан, олох хэцүү
Гэтэл өөр нэг сонин ертөнц бий. Зарим асуудалд:
- Хариуг хэн нэгэн өгчихвөл: “зөв үү, буруу юу” гэдгийг шалгах маш амархан
- Харин хариуг нь өөрөө олъё гэвэл: боломжит бүх хувилбарыг шалгах шаардлагатай
Энд бодох хугацаа огцом өсдөг. Жишээ нь, Sudoku бодлого. Бэлэн бөглөсөн хүснэгтийг хараад зөв эсэхийг шалгах амархан. Гэхдээ хоосон Sudoku-г эхнээс нь бодъё гэвэл буруу хувилбар бүрийг шалгах хэрэг гарна.
Ийм төрлийн асуудлуудыг NP ангилал гэдэг.
Хэрвээ хариуг нь хурдан шалгаж болдог бол,
хариуг нь хурдан олж болох уу?
Хэрвээ тийм бол — P = NP.
Хэрвээ үгүй бол — P ≠ NP.
NP – Complete
NP-бүрэн (NP-complete) гэдэг нь компьютерийн шинжлэх ухааны хамгийн хүнд бодлогуудын ангилал юм. Хэрэв энэ ангиллын ердөө ганц бодлогыг л “хурдан” (полиноминал хугацаанд) шийдэх арга олдож чадвал NP ангиллын бүх бодлогыг хурдан шийдэж болно гэсэн үг.
Бодлого NP-бүрэн байхын тулд дараах хоёр нөхцөлийг хангах ёстой:
- NP-хүнд (NP-hard) байх: NP ангиллын бусад бүх бодлогыг энэ бодлого руу хөрвүүлж (reduction) шийдэж болдог байх.
- NP ангилалд багтах: Өгөгдсөн хариулт зөв эсэхийг маш хурдан (полиноминал хугацаанд) шалгаж болдог байх.
NP-Complete бодлогын гол онцлог нь:
- NP доторх бүх бодлогыг түүн рүү “хөрвүүлж” болдог
- Тиймээс нэгийг нь хурдан бодвол, бүгд хурдан болно
Энэ нь нэг түлхүүр бүх хаалгыг онгойлгохтой адил. Иймээс NP-бүрэн бодлого бол нэг бодлогын тухай биш, бүх бодлогын хувь заяаны тухай ойлголт юм.
Яагаад 50 гаруй жил хэн ч шийдэж чадаагүй вэ?
Энэ асуултыг анх 1970-аад онд томъёолсноос хойш дэлхийн хамгийн ухаантай математикч, компьютерийн онолчид бүгд оролдсон. Гэхдээ өнөөдрийг хүртэл хэн ч баттай хариу өгч чадаагүй.
Яагаад гэвэл энэ бол “илүү хурдан компьютер” авах тухай асуудал биш. Илүү их дата, илүү хүчтэй процессор, бүр квант компьютер байсан ч логикийн хязгаар өөрөө хэвээрээ үлдэнэ.
Энд “энэ бодлогыг ингэж бодож чадна” гэж жишээ гаргах нь хангалтгүй. Харин “ямар ч аргаар ингэж бодож болохгүй” гэдгийг батлах ёстой. Ийм баталгаа бол математикийн хамгийн хэцүү хэлбэрийн нэг.
Товчхондоо, бид энэ асуултыг шийдэхэд хангалттай “оюуны зэвсэг” одоогоор олж чадаагүй байгаа.
Хэрвээ нэг өдөр шийдэгдчихвэл юу болох вэ?
Хоёр өөр ирээдүй бий.
Хэрвээ P = NP гэдгийг баталбал, өнөөдрийн интернетийн аюулгүй байдлын суурь ганхана. Нууц үг, банк, цахим гарын үсэг зэрэг олон систем үндсээрээ өөрчлөгдөнө. Үүний зэрэгцээ эмийн судалгаа, логистик, хиймэл оюун ухаан асар хурдтай хөгжнө. Одоо “боломжгүй” гэж үздэг олон асуудал гэнэт “амархан” болно.
Харин P ≠ NP гэдгийг баталбал, эсрэгээрээ бид тайвширч чадна. Зарим асуудал угаасаа хэцүү, түүнийг хэзээ ч бүрэн автоматжуулж болохгүй гэдэг нь баталгаажна. Интернетийн аюулгүй байдал онолын хувьд бат бөх болно. Хүн ба машины хязгаар тодорхой болно.
Эцэст нь хэлэхэд…
P vs NP бол зүгээр нэг компьютерийн онол биш.
Энэ бол оюун ухаан гэж юу вэ, бодох гэдэг зүйлд хязгаар байдаг уу гэсэн асуулт.
Магадгүй бид зарим асуултад “удаан” биш, харин “боломжгүй” гэсэн хариуг л хүлээн зөвшөөрөх ёстой.
Боловсролыг инженерчлэв.
