NP анги нь "тодорхой бус олон гишүүнт цаг" гэсэн утгатай бөгөөд онолын компьютерийн шинжлэх ухааны дэд салбар болох тооцооллын нарийн төвөгтэй байдлын онолын үндсэн ойлголт юм. БЦГ-ыг ойлгохын тулд эхлээд тийм эсвэл үгүй гэсэн хариулттай асуултууд болох шийдвэр гаргах асуудлын тухай ойлголтыг ойлгох хэрэгтэй. Энэ контекст дэх хэл нь зарим цагаан толгойн дээрх мөрүүдийн багцыг хэлдэг бөгөөд мөр бүр шийдвэрийн асуудлын жишээг кодлодог.
Хэрэв (L) олон гишүүнт цаг хугацааны шалгагч байгаа бол хэлийг (L) NP хэлээр хэлнэ. Шалгагч нь тодорхойлогч алгоритм (V) бөгөөд жишээ (x) ба гэрчилгээ (y) гэсэн хоёр оролтыг авдаг. Гэрчилгээг (y) мөн "гэрч" эсвэл "нотолгоо" гэж нэрлэдэг. Баталгаажуулагч (V) нь гэрчилгээ (y) нь (x) хэл (L)-д хамаарах эсэхийг шалгадаг. Албан ёсоор хэл (L) нь олон гишүүнт-цаг хугацааны алгоритм (V) ба олон гишүүнт (p(n)) байвал NP-д байдаг бөгөөд ингэснээр мөр бүрт (L-д x) (y) тэмдэгттэй мөр (y) байдаг. |y|.leq p(|x|)) ба (V(x, y) = 1). Үүний эсрэгээр (x notin L) тэмдэгт мөр бүрт (V(x, y) = 1) тэмдэгт мөр (y) байхгүй.
Энэ үзэл баримтлалыг тодруулахын тулд "Булийн сэтгэл ханамж" (SAT) гэсэн алдартай асуудлыг авч үзье. SAT асуудал нь тухайн Boolean томьёо дахь хувьсагчид үнэний утгын хуваарилалт байгаа эсэхийг асууж, томъёог үнэн гэж үнэлдэг. SAT асуудал нь NP-д байгаа учир нь логикийн томьёо ( phi ) ба түүний хувьсагчдад үнэний утгуудын хуваарилалт ( альфа ) өгөгдсөн бол ( alpha ) ( phi ) хангагдсан эсэхийг олон гишүүнт хугацаанд шалгаж болно. Энд жишээ ( x ) нь Булийн томъёо ( phi ), гэрчилгээ ( y ) нь даалгавар ( альфа ) байна. Шалгагч ( V ) нь ( alpha ) ( phi ) үнэн эсэхийг шалгадаг бөгөөд үүнийг ( phi ) -ийн хэмжээтэй холбоотой олон гишүүнт хугацаанд хийж болно.
Өөр нэг тод жишээ бол "Гамильтоны зам"-ын асуудал юм. Энэ асуудал нь өгөгдсөн графикт орой бүр дээр яг нэг удаа очдог зам байгаа эсэхийг асууна. График ( G ) ба оройнуудын дараалал ( P ) өгөгдсөн учраас ( P ) нь ( G ) дахь Гамильтоны зам мөн эсэхийг олон гишүүнт хугацаанд шалгаж болох тул Гамильтоны замын бодлого NP-д байна. Энэ тохиолдолд жишээ ( x ) нь график ( G ), гэрчилгээ ( y ) нь оройнуудын дараалал ( P ) байна. Шалгагч ( V ) нь ( P ) нь Гамильтоны замыг үүсгэж байгаа эсэхийг шалгадаг бөгөөд үүнийг ( G ) -ийн хэмжээтэй холбоотой олон гишүүнт хугацаанд хийж болно.
Олон гишүүнт-цаг хугацааны баталгаажуулалтын тухай ойлголт нь тооцооллын хувьд боломжгүй байсан ч гэсэн үр дүнтэй шалгах боломжтой асуудлуудыг тодорхойлох арга замыг өгдөг учраас чухал юм. Энэ нь олон гишүүнт хугацаанд шийдлийг шалгаж болох бодлого бүрийг олон гишүүнт хугацаанд шийдэж болох уу гэсэн ( P = NP ) гэсэн алдартай асуултад хүргэдэг. Анги ( P ) нь детерминист Тьюрингийн машинаар олон гишүүнт хугацаанд шийдэж болох шийдвэрийн бодлогуудаас бүрдэнэ. Хэрэв ( P = NP ) бол олон гишүүнт цаг хугацааны шалгагчтай бодлого бүр олон гишүүнт цаг хугацааны шийдэгчтэй байна гэсэн үг юм. Энэ асуулт компьютерийн шинжлэх ухааны хамгийн чухал нээлттэй асуудлын нэг хэвээр байна.
NP-ийн гол шинж чанаруудын нэг нь олон гишүүнт цаг хугацааны бууралтад хаалттай байдаг. Хэлнээс ( L_1 ) хэл рүү ( L_2 ) олон гишүүнт цаг хугацааны бууралт нь олон гишүүнт хугацааны тооцоологдох функц ( f ) бөгөөд ( L_1 дэх x ) зөвхөн ( L_2 дахь f(x) ). Хэрэв ( L_1 ) -ээс ( L_2 ) хүртэл олон гишүүнт хугацааны бууралт байгаа бол ( L_2 ) нь NP-д байгаа бол ( L_1 ) нь мөн NP-д байна. Энэ шинж чанар нь NP-ийн "хамгийн хэцүү" асуудлуудыг тодорхойлдог NP-бүрэн байдлыг судлахад чухал ач холбогдолтой юм. Бодлого нь NP-д байгаа бол NP-бүрэн гэсэн үг бөгөөд NP-ийн бодлого бүрийг олон гишүүнт хугацаанд бууруулж болно. SAT-ийн асуудал нь NP-бүрэн болох нь батлагдсан анхны асуудал байсан бөгөөд энэ нь бусад асуудлуудын NP-бүрэн байдлыг нотлох үндэс болдог.
Олон гишүүнт-цаг хугацааны баталгаажуулалтын тухай ойлголтыг илүү харуулахын тулд "Дэд олонлогийн нийлбэр" бодлогыг авч үзье. Энэ асуудал нь өгөгдсөн зорилтот утгад нийлдэг бүхэл тоонуудын дэд олонлог байгаа эсэхийг асууна. Бүхэл тоо ( S ), зорилтот утга ( t ) болон ( S ) -ийн дэд олонлог ( S' ) өгөгдвөл олон гишүүнт хугацаанд доторх элементүүдийн нийлбэр байгаа эсэхийг шалгах боломжтой тул Дэд олонлогийн нийлбэр бодлого NP дээр байна. ( S' ) тэнцүү ( t ). Энд жишээ ( x ) нь хос ( (S, t) ), гэрчилгээ ( y ) нь дэд олонлог ( S' ) байна. Шалгагч ( V ) нь ( S' ) дахь элементүүдийн нийлбэр нь ( t ) тэнцүү эсэхийг шалгадаг бөгөөд үүнийг ( S ) -ийн хэмжээтэй холбоотой олон гишүүнт хугацаанд хийж болно.
Олон гишүүнт-цаг хугацааны баталгаажуулалтын ач холбогдол нь онолын үүднээс авч үзэхээс давж гардаг. Практикийн хувьд энэ нь БЦГ-ын асуудалд санал болгож буй шийдлийг (сертификат) өгсөн бол үр дүнтэй шалгаж болно гэсэн үг юм. Энэ нь криптографийн протоколууд, оновчлолын асуудал, шийдлийн зөв эсэхийг шалгах нь чухал байдаг янз бүрийн талбаруудад ихээхэн нөлөө үзүүлдэг.
Дүгнэж хэлэхэд, NP анги нь шийдлийг олон гишүүнт хугацаанд детерминист алгоритмаар шалгаж болох шийдвэрийн бодлогуудыг багтаадаг. Энэхүү ойлголт нь тооцооллын нарийн төвөгтэй байдлын онолын үндэс суурь бөгөөд компьютерийн шинжлэх ухааны онолын болон практикийн аль алинд нь гүн гүнзгий нөлөө үзүүлдэг. NP, олон гишүүнт-цаг хугацааны баталгаажуулалт, NP-бүрэн байдал зэрэг холбогдох ухагдахуунуудыг судлах нь судалгааны идэвхтэй бөгөөд чухал талбар хэвээр байна.
Сүүлийн үеийн бусад асуулт, хариулт Харьцуулалт:
- PSPACE анги нь EXPSPACE ангитай тэнцэхгүй байна уу?
- P нарийн төвөгтэй байдлын анги нь PSPACE ангийн дэд олонлог мөн үү?
- Детерминист TM дээр ямар ч NP бүрэн бодлогын үр ашигтай олон гишүүнт шийдийг олсноор Np ба P анги ижил гэдгийг баталж чадах уу?
- NP анги нь EXPTIME ангитай тэнцүү байж чадах уу?
- PSPACE-д тодорхой NP алгоритм байхгүй асуудал байна уу?
- SAT-ийн асуудал нь NP-ийн бүрэн асуудал байж болох уу?
- Хэрэв олон гишүүнт хугацаанд шийдвэрлэх тодорхой бус турингийн машин байгаа бол асуудал NP нарийн төвөгтэй байдлын ангилалд байж болох уу?
- P болон NP нь яг ижил нарийн төвөгтэй байдлын анги мөн үү?
- P төвөгтэй байдлын ангид контекстгүй хэл бүр байдаг уу?
- NP-г олон гишүүнт-цаг хугацааны шалгагчтай шийдвэрийн бодлогуудын анги гэж тодорхойлсон нь P ангиллын бодлогод олон гишүүнт-цаг хугацааны шалгагчтай байдгийн хооронд зөрчилдөөн байна уу?
Илүү олон асуулт, хариултыг Нарийн төвөгтэй байдлаас харна уу