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

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

Aмалий нуқтаи назардан қизиқ бўлган вазифаларнинг аксарияти, полиномиаль (полиномиаль вақт мобайнида ишловчи) алгоритмлар. Яъни, n узунликдаги киришда алгоритмнинг ишлаш вақти доимий k (кириш узунлигидан мустақил) учун O(nk) дан ошмайди. Ҳар бир масалада ушбу хусусиятни қондирадиган ечим алгоритми мавжуд эмас. Баъзи масалаларни умуман бирон бир алгоритм ёрдамида ҳал қилиб бўлмайди. Бундай масаланинг классик мисоли бу “тўхташ муаммоси” (берилган дастур берилган киришда тўхташини билиш). Бундан ташқари, уларни ҳал қиладиган алгоритм мавжуд бўлган масалалар мавжуд, ҳар қандай бундай алгоритм узоқ вақт ишлайди – унинг ишлаш вақти ҳар қандай фиксирланган k сони учун O(nk) бўла олмади.

Aгар биз амалий алгоритмлар ва фақат назарий қизиқиш алгоритмлари ўртасида қўпол, аммо расмий чегара чизишни истасак, унда кўпликли вақт ичида ишлайдиган алгоритмлар синфи биринчи ўринда туради. NP -тўлиқ деб номланган масалалар синфини кўриб чиқамиз. Ушбу масалалар учун ҳеч қандай полиномиаль алгоритмлар топилмаган, аммо бундай алгоритмлар мавжуд эмаслиги исботланмади. NP билан боғлиқ муаммоларни ўрганиш “P = NP” деб номланган савол билан боғлиқ. Бу савол 1971 йилда берилган ва ҳозирда ҳисоблаш назариясида энг қийин масалалардан бири ҳисобланади.

Нима учун дастурчи NP – тугалланган масалалар ҳақида билиши керак? Aгар бирон бир NP – тўлиқлик учун унинг тўлиқлигини исботлаш мумкин бўлса, уни деярли ҳал қилиб бўлмайди деб ҳисоблаш учун асос бор. Бундай ҳолда, уни аниқ ҳал қиладиган тезкор алгоритмни қидиришни давом эттиришдан кўра, тахминий алгоритмни тузишга вақт сарфлаш яхшироқдир.

Полином вақти

Абстракт масалалар

Юқорида айтиб ўтилганидек, кўп жиҳатдан ҳал қилинадиган (полиномиал) масалалар концепцияси амалда ечилиши мумкин бўлган масалалар ғоясини такомиллаштириш ҳисобланади. Ушбу келишувни нима тушунтиради? Биринчидан, амалда ишлатиладиган кўпайтирилган алгоритмлар, одатда жуда тез ишлайди. Иккинчидан, полиномиал алгоритмлар синфини кўриб чиқиш, бу синфнинг ҳажми маълум бир ҳисоблаш моделини танлашдан деярли мустақил бўлишидир. Масалан, тасодифий тасодифий кириш машинасида (RAM) кўпайтирилган вақт ичида ечилиши мумкин бўлган масалалар синфи Тьюринг машиналарида полиномал ечиладиган масалалар синфига тўғри келади. Синф параллел ҳисоблаш модели учун бир хил бўлади, процессорлар сони, кириш узунлиги полиноми билан чекланган. Учинчидан, полиномал ечиладиган масалалар синфи табиий ёпиқлик хусусиятларига эга. Масалан, иккита алгоритмнинг таркибикомпозицияси ҳам полиномиал вақтли ишлайди. Бунинг сабаби, кўпхадларнинг йиғиндиси, кўпайтмаси ва композицияси кўпхадрдир.