Np-тўликлик масаласи

NP- туликлик масаласи — алгоритмлар назариясида NP – синфдаги «ҳа» ёки «йўк» жавобли масалани шу синфдаги бошка масалага полиномиаль вакт оралгида мослаштириш мумкин (яни, бошлангич маълумотлар хажмига богланганлик даражаси маълум полинимдан катта булмаган амаллар ёрдамида бажарилади).

Шундай қилиб, NP -тўлиқ масалалар, маълум маънода, NP синфидаги “типик” масалалар тўпламини шакллантиради: агар уларнинг баъзилари учун "тезкор" ечим алгоритми топилса, NP синфидаги ҳар қандай бошқа масалани худди шу тарзда ҳал қилиш мумкин.

Формаль таъриф

Aлифбо деганда ҳар қандай чекланган белгилар тўплами тушунилади (масалан, {0, 1} ёки {a, b, c}). Ихтиёрий алифбосидан тузилган барча сўзлар тўплами (ёзилган сатирлар, ушбу алифбонинг белгиларидан ташкил топади) ∑* билан белгиланади.

∑ aлфавит ёрдамида яратилган ихтиёрий L тили бу тўпламнинг L тўплам остиси, яъни L⸦.

учун таниб олиш вазифаси берилган сўз тилига тегишли ёки йўқлигини аниқлашдир.

∑ aлифбо устида ва L2 - иккита тил бўлсин. L1 тилига (Карп бўйича) L2 тилига қисқартириш дейилади, агар функцияси мавжуд бўлса, бу функцияни полиномиаль вақт билан ҳисоблаш мумкин бўлса, қуйидаги хусусиятга ега: x ∈ L1, , агар ва фақат агар f(x)∈L2, . Карп бўйича қисқартириш L1≤pL2 билан белгиланади.

 

Aгар NP-дан бирон бир тил унга қисқартирилса, L2 тили NP-тўлиқ деб номланади. Тил NP-мукаммал деб номланади, агар у NP-қийин бўлса ва шу билан бирга ўзи NP синфида бўлса.

A масала Б масаласига қисқартирилганлиги, A масала Б масаласидан кўра “мураккаброқ” эканлигини англатади (чунки агар биз Б масалани ечилиши, A масаланини ҳам ечилишини билдиради). Шундай қилиб, NP билан боғлиқ қийинчиликлар синфга NP билан боғлиқ масалалар ва улар учун "анча қийин" бўлган масалалар киради (яъни NP билан боғлиқ масалаларни камайтириш мумкин бўлган масалалар). NP синф NP тўлиқ масалаларни ва улардан "осонроқ" бўлган масалаларни ўз ичига олади (яъни, NP-тўлиқ масалаларга қисқартиришган масалалар).