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

Қуйида ҳисоблаш масаласининг абстракт моделини келтирилган. Буни абстракт масала деб номлаймиз, Q – иккита тўплам элементлари орасидаги ихтиёрий бинар муносабат: I – шартлар тўплами ва S – ечимлар тўплами. Масалан, G = (V, E) йўналтирилмаган графнинг берилган иккита учлари орасидаги энг қисқа йўлни топиш масаласида, шарт (элемент I) уч элемент, граф ва иккита қиррадан иборат ва ечим (S лемент) – бу графда керакли йўлни ташкил этувчи вертикалларнинг кетма-кетлиги.

NP тўлиқлиги назариясида фақат ҳал қилиш масалалари кўриб чиқилади – муайян саволга “ҳа” ёки “йўқ” деб жавоб бериш керак бўлган масалалар. Расман, I тўплам шартларини {0, 1} тўпламга тўғри келадиган функция сифатида кўриб чиқилиши мумкин. Масалан, G = (V, E) графдаги энг қисқа йўлни топиш масаласи билан берилган G=(V, E) граф ёрдамида иккита тугун u, v ∈ V ва натурал k бутун сонлар u ва v тугунлари орасида ундан катта бўлмаган ҳамда G графда йўл бор ёки йўқлиги масаласини ечинг.

Оптималлаштириш билан боғлиқ масалалар бу – муайян миқдордаги қийматни максимал даражада ошириш ёки минималлаштириш керак бўлган масалаларди. NP – тўлиқлик ҳақида савол беришдан олдин бундай масалалар, уларни ҳал қилиш масалаларига айлантирилиши керак. Шундай қилиб, масалан, графдаги энг қисқа йўлни топиш масаласида оптималлаштириш масаласини ечиш масаласидан рухсат бериш масаласига ўтдик ва йўл узунлигига чеклов қўшдик. Aгар трансформациядан кейин NP – тўлиқ масаласи юзага келса, унда асл муаммонинг қийинлиги ҳам белгиланади.

Маълумотлар тақдимоти

Кириш маълумотларини (яъни I тўпламнинг элементи) алгоритмга киритишдан олдин уларнинг қандай қилиб “компютерга қулай” тарзда тақдим этилиши тўғрисида келишиб олиш керак. Дастлабки маълумотлар битлар кетма-кетлиги билан кодланган деб қабул қиламиз. Формал айтганда, S тўпламининг элементларини ифодалаш бу S дан e ни битли сатрлар тўпламларига тушишидир. Масалан, (0, 1, 2, 3,...) – бутун сонларни, одатда (0, 1, 10, 11, 100, ...) – битли сатрлар билан ифодаланади.