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

Тақдим қилинган маълумотларни жойлаштирб, мавҳум масалани сатрли маълумотга айлантирамиз, бу сатирли маълумот учун кириш маълумотлари, масаланинг дастлабки маълумотларини акс эттирувчи битли сатир бўлади. Кириш маълумотлари (битли сатр) n – узунликда бўлганида, алгоритмнинг ишлаш вақти O(T(n)) – бўлса, алгоритм сатирли масалани O(T(n)) вақтда ечади десак бўлади. Aгар k константа ва O(T(n)) вақт ичида бу масалани ечадиган алгоритм мавжуд бўлса, сатирли масала полиномиаль деб аталади. Мураккаблик P синфи – бу барча сатирли масалалар бўлиб, полономиаь вақт ичида ечилиши мумкин, яъни, O(nk) вақт ичида ечилиши мумкин, бу ерда k киришга боғлиқ бўлмайди.

Полиномиал абстракт масаласининг концепциясини аниқлашни истаган ҳолда, биз турли хил маълумотларни тақдим этиш мумкинлигига дуч келамиз.

Хар бир тақдим қилинган e тўплам учун, I киришлари бўлган Q абстракт масаланинг сатирли масаласини оламиз.

Бироқ, амалда (асоси 1 бўлган рақамли тизим каби “қиммат” вакиллик усулларини истисно қилсак), табиий вакиллик усуллари одатда эквивалентдир, чунки уларни бир-бирига кўп жиҳатдан айлантириш мумкин. A полиномиал алгоритми мавжуд бўлса, f:{0,1}*→{0,1}* функцияси полинимиал вақт ичида ҳисоблаб чиқилади, у ҳар қандай x∈ {0,1}* учун f(x) натижани беради.

Ихтиёрий абстракт масала учун I тўплами шаритларини кўриб чиқамиз. I тўпламнинг е1 ва е2 элементлари полиномиаль боғланган дейилади, aгар полиномиаль вақтда ҳисоблаш мумкин бўлган иккита f12(e1(i)) = e2(i) ва f21(e2(i)) = e1(i), i ∈ I фунциялар мавжуд бўлса. Бундай ҳолларда, полиномиаль боғланган иккита элементдан қайси бирини танлаш муҳим эмас.

 P, NP, NP-complete (NP-тўликлик масалалари) синфлар орасидаги муносабатлар, NP-hard (NP-мураккаб масалалар), P≠NP ва P=NP бўлган холларда.