P болон NP нь яг ижил нарийн төвөгтэй байдлын анги мөн үү?
P нь NP-тэй тэнцэх эсэх нь компьютерийн шинжлэх ухаан, математикийн хамгийн гүнзгий бөгөөд шийдэгдээгүй асуудлын нэг юм. Энэ асуудал нь тооцооллын нарийн төвөгтэй байдлын онолын цөмд оршдог бөгөөд энэ нь тооцооллын асуудлуудын төрөлхийн хүндрэлийг судалж, тэдгээрийг шийдвэрлэхэд шаардлагатай нөөцийн дагуу ангилдаг.
Асуултыг ойлгохын тулд P ба NP ангиллын тодорхойлолтыг ойлгох нь чухал юм. P ангилал нь олон гишүүнт цаг хугацаанд детерминист Тьюрингийн машинаар шийдэж болох шийдвэр гаргах бодлого (тийм/үгүй гэсэн хариулттай бодлого)-аас бүрдэнэ. Олон гишүүнт хугацаа гэдэг нь асуудлыг шийдвэрлэхэд шаардагдах хугацааг оролтын хэмжээний олон гишүүнт функцээр илэрхийлж болно гэсэн үг юм. P хэл дээрх асуудлын жишээнд тоонуудын жагсаалтыг эрэмбэлэх (үүнийг нэгтгэх гэх мэт үр ашигтай алгоритмуудыг ашиглан O(n log n) хугацаанд хийж болно) болон Евклидийн алгоритмыг (O(log дээр ажилладаг)) ашиглан хоёр бүхэл тооны хамгийн том нийтлэг хуваагчийг олох зэрэг орно. (мин(а, б))) цаг).
Нөгөө талаас NP анги нь өгөгдсөн шийдлийг детерминист Тьюрингийн машинаар олон гишүүнт хугацаанд шалгаж болох шийдвэрийн бодлогуудаас бүрддэг. Энэ нь хэн нэгэн асуудалд нэр дэвшигчийн шийдлийг гаргаж өгвөл түүний зөв эсэхийг үр дүнтэй шалгаж болно гэсэн үг юм. Хамгийн чухал нь NP гэдэг нь асуудлыг өөрөө олон гишүүнт хугацаанд шийдэж болно гэсэн үг биш, зөвхөн санал болгож буй шийдлийг хурдан шалгаж болно гэсэн үг юм. NP-ийн асуудлын жишээнд өгөгдсөн Булийн томьёог үнэн болгох хувьсагчдад үнэний утгын хуваарилалт байгаа эсэхийг тодорхойлохыг эрэлхийлдэг Булийн ханамжийн бодлого (SAT) болон мөчлөг байгаа эсэхийг асуудаг Гамильтоны мөчлөгийн бодлого орно. Графикийн орой бүрт яг нэг удаа очдог.
P vs NP асуулт нь шийдлийг олон гишүүнт хугацаанд (өөрөөр хэлбэл NP дэх бодлого бүрийг) шалгаж болох бодлого бүрийг олон гишүүнт хугацаанд шийдэж чадах эсэхийг (өөрөөр хэлбэл P дээр байгаа) асуудаг. Албан ёсоор бол P = NP эсэх асуудал байна. Хэрэв P нь NP-тэй тэнцүү байсан бол энэ нь шийдлийг хурдан шалгах боломжтой бүх асуудлыг хурдан шийдвэрлэх боломжтой гэсэн үг юм. Энэ нь криптограф, оновчлол, хиймэл оюун ухаан зэрэг салбарт гүн гүнзгий нөлөө үзүүлэх болно, учир нь одоогийн байдлаар шийдвэрлэх боломжгүй олон асуудлыг үр дүнтэй шийдвэрлэх боломжтой болно.
Олон арван жилийн судалгааг үл харгалзан P vs NP асуулт нээлттэй хэвээр байна. Одоогоор хэн ч P = NP эсвэл P ≠ NP гэдгийг баталж чадаагүй байна. Энэ асуудлыг Клэй Математикийн Хүрээлэнгээс гаргасан "Мянганы шагналын долоон асуудал"-ын нэг болгож, зөв шийдэлд нь нэг сая долларын шагнал олгохоор оруулсан нь энэ асуудлын хүндрэлтэй байгааг онцолж байна. Шийдвэр гаргаагүй нь онолын болон хэрэглээний компьютерийн шинжлэх ухааны аль алиных нь хувьд мэдэгдэхүйц хөгжилд хүргэсэн.
P vs NP асуулттай холбоотой гол ойлголтуудын нэг бол NP-бүрэн байдал юм. Бодлого нь NP-д байгаа бол NP-бүрэн, харин NP-ийн аливаа бодлоготой адил хэцүү, учир нь аливаа NP бодлогыг олон гишүүнт-хугацааны бууралтыг ашиглан багасгаж болно гэсэн утгаараа. NP-бүрэн байдлын тухай ойлголтыг Стивен Күүк 1971 онд гаргасан илтгэлдээ танилцуулж, SAT-ийн асуудал нь NP-бүрэн гэдгийг нотолсон. Күүкийн теорем гэгддэг энэхүү үр дүн нь NP-бүрэн бодлогын тодорхой жишээг өгч, бусад NP-бүрэн бодлогуудыг тодорхойлох хүрээг бий болгосон тул шинэлэг зүйл байв.
Түүнээс хойш явуулын худалдагчийн асуудал, бүлгэмийн асуудал, үүргэвчний асуудал гэх мэт бусад олон асуудлууд нь NP- бүрэн гүйцэд болох нь нотлогдсон. NP-бүрэн байдлын ач холбогдол нь хэрэв аливаа NP-бүрэн бодлогыг олон гишүүнт хугацаанд шийдэж чадвал NP-ийн бүх асуудлыг олон гишүүнт хугацаанд шийдэж болох бөгөөд энэ нь P = NP гэсэн үг юм. Эсрэгээр, хэрэв олон гишүүнт хугацаанд ямар нэгэн NP-бүрэн асуудлыг шийдэж чадахгүй бол P ≠ NP болно.
NP-бүрэн байдлын тухай ойлголтыг харуулахын тулд аялагч борлуулагчийн асуудлыг (TSP) авч үзье. Энэ асуудалд худалдагч тодорхой хотуудад яг нэг удаа очиж, аялалын нийт зайг багасгах зорилготойгоор анхны хот руугаа буцах ёстой. TSP-ийн шийдвэрийн хувилбар нь өгөгдсөн утгаас бага эсвэл тэнцүү нийт зайтай хотуудын аялал байгаа эсэхийг асуудаг. Энэ асуудал БЦГ-т байгаа учир нь санал болгож буй аялалд тухайн аялал нь зайны хязгаарлалтыг хангаж байгаа эсэхийг олон гишүүнт хугацаанд хялбархан шалгаж болно. Түүнчлэн, NP-ийн аливаа асуудлыг олон гишүүнт цагийн TSP-ийн жишээ болгон хувиргаж болох тул TSP нь NP- бүрэн юм.
Өөр нэг жишээ бол өгөгдсөн график нь заасан хэмжээтэй бүрэн дэд график (клик) агуулж байгаа эсэхийг асуудаг бүлэглэлийн бодлого юм. Нэр дэвшигчдийн бүлгийг харгалзан үзвэл энэ нь үнэхээр шаардлагатай хэмжээний бүлэг мөн эсэхийг олон гишүүнт хугацаанд шалгаж болох тул энэ асуудал NP-д байгаа юм. Кликийн асуудал нь мөн NP- бүрэн бөгөөд үүнийг үр дүнтэй шийдвэрлэх нь БЦГ-ын бүх асуудлыг үр дүнтэй шийдвэрлэх боломжтой гэсэн үг юм.
P vs NP болон NP-бүрэн байдлыг судлах нь онолын компьютерийн шинжлэх ухаанд янз бүрийн арга техник, хэрэгслийг хөгжүүлэхэд хүргэсэн. Ийм аргуудын нэг нь нэг бодлого нь нөгөөгөөсөө дутуугүй хэцүү гэдгийг харуулахын тулд олон гишүүнт цаг хугацааны бууралтын тухай ойлголт юм. А бодлогоос Б бодлого руу олон гишүүнт цагийн бууралт гэдэг нь олон гишүүнт цагийн дотор А-ийн тохиолдлуудыг B-ийн жишээ болгон хувиргах хувиргалт бөгөөд ингэснээр В-ийн хувиргасан жишээний шийдлийг А-ийн анхны жишээг шийдвэрлэхэд ашиглаж болно. А-г олон гишүүнт хугацаанд, В-г олон гишүүнт хугацаанд, А-г олон гишүүнт хугацаанд шийдэж болно.
Өөр нэг чухал ухагдахуун бол NP-хэцүү бодлогуудыг (ядаж NP-иж бүрэн бодлоготой адил хэцүү асуудлууд) олон гишүүнт хугацаанд бараг оновчтой шийдлээр хангадаг ойролцоолох алгоритмын тухай ойлголт юм. Эдгээр алгоритмууд нь яг оновчтой шийдлийг олох албагүй ч хамгийн сайнд ойртсон шийдлүүдийг санал болгодог. Жишээлбэл, аялагч худалдагчийн асуудал нь метрик TSP-ийн (зай нь гурвалжингийн тэгш бус байдлыг хангадаг) оновчтой аяллын 1.5 хүчин зүйлийн дотор аяллыг баталгаажуулдаг сайн мэддэг ойролцоолох алгоритмтай байдаг.
P ба NP асуултыг шийдвэрлэх үр дагавар нь онолын компьютерийн шинжлэх ухаанаас давж гардаг. Криптографийн хувьд олон шифрлэлтийн схемүүд нь бүхэл тоон хүчин зүйлчлэл, дискрет логарифм гэх мэт тодорхой асуудлын хатуулагт тулгуурладаг бөгөөд эдгээр нь NP-д биш харин P-д байдаг гэж үздэг. Хэрэв P нь NP-тэй тэнцүү байсан бол эдгээр асуудлыг үр ашигтайгаар шийдэж болох бөгөөд энэ нь эвдрэлд хүргэж болзошгүй юм. криптографийн системийн аюулгүй байдал. Үүний эсрэгээр, P ≠ NP гэдгийг нотлох нь ийм системийн аюулгүй байдлын илүү бат бөх суурийг бий болгоно.
Оновчлолд хуваарь, чиглүүлэлт, нөөцийн хуваарилалт гэх мэт олон бодит асуудлуудыг NP-хүнд бодлого болгон загварчилсан байдаг. Хэрэв P нь NP-тэй тэнцүү байсан бол эдгээр асуудлыг оновчтой шийдвэрлэх үр ашигтай алгоритмуудыг боловсруулж, янз бүрийн салбарт мэдэгдэхүйц ахиц дэвшил гаргах боломжтой гэсэн үг юм. Гэсэн хэдий ч P ≠ NP гэсэн одоогийн таамаглал нь эдгээр асуудлыг шийдвэрлэх практик шийдлүүдийг хангадаг эвристик болон ойролцоолсон алгоритмуудыг хөгжүүлэхэд хүргэсэн.
P vs NP асуулт нь математик үнэний мөн чанар, хүний мэдлэгийн хязгаарыг хөндсөн тул философийн ач холбогдолтой. Хэрэв P нь NP-тэй тэнцүү байсан бол энэ нь богино нотолгоог агуулсан математик хэллэг бүрийг үр дүнтэйгээр нээж, математикийн нээлтийн үйл явцыг өөрчлөх боломжтой гэсэн үг юм. Нөгөөтэйгүүр, хэрэв P ≠ NP бол үр ашигтайгаар тооцоолж, баталгаажуулах боломжууд нь тодорхой хязгаарлалттай болохыг харуулж, математикийн бүтцийн нарийн төвөгтэй байдал, баялаг байдлыг онцлон харуулах болно.
P ба NP гэсэн асуултад тодорхой хариулт байхгүй байсан ч түүнийг тойрсон судалгаа нь тооцооллын нарийн төвөгтэй байдлын талаар илүү гүнзгий ойлголттой болж, компьютерийн шинжлэх ухаанд гүнзгий нөлөө үзүүлсэн олон техник, хэрэгслийг хөгжүүлэхэд хүргэсэн. Энэ асуултыг шийдвэрлэх эрэл хайгуул нь судлаачдыг урамшуулж, сорилтод хүргэж, энэ салбарт ахиц дэвшил гаргаж, тооцооллын үндсэн хязгаарын талаарх бидний ойлголтыг өргөжүүлсээр байна.
Сүүлийн үеийн бусад асуулт, хариулт Харьцуулалт:
- PSPACE анги нь EXPSPACE ангитай тэнцэхгүй байна уу?
- P нарийн төвөгтэй байдлын анги нь PSPACE ангийн дэд олонлог мөн үү?
- Детерминист TM дээр ямар ч NP бүрэн бодлогын үр ашигтай олон гишүүнт шийдийг олсноор Np ба P анги ижил гэдгийг баталж чадах уу?
- NP анги нь EXPTIME ангитай тэнцүү байж чадах уу?
- PSPACE-д тодорхой NP алгоритм байхгүй асуудал байна уу?
- SAT-ийн асуудал нь NP-ийн бүрэн асуудал байж болох уу?
- Хэрэв олон гишүүнт хугацаанд шийдвэрлэх тодорхой бус турингийн машин байгаа бол асуудал NP нарийн төвөгтэй байдлын ангилалд байж болох уу?
- NP нь олон гишүүнт цаг шалгагчтай хэлний анги юм
- P төвөгтэй байдлын ангид контекстгүй хэл бүр байдаг уу?
- NP-г олон гишүүнт-цаг хугацааны шалгагчтай шийдвэрийн бодлогуудын анги гэж тодорхойлсон нь P ангиллын бодлогод олон гишүүнт-цаг хугацааны шалгагчтай байдгийн хооронд зөрчилдөөн байна уу?
Илүү олон асуулт, хариултыг Нарийн төвөгтэй байдлаас харна уу