Кіріспе

Есептеу күрделілігі теориясында NP эквиваленттілік класы – NP оңай және NP қиын функциялық проблемалар жиынтығы. NP эквиваленттілігі – функциялық проблемалар үшін NP толықтығының аналогы. Мысалы, FIND SUBSET SUM (қосындыны табу) проблемасы NP эквивалентті. Бүтін сандар жиынтығы берілгенде, FIND SUBSET SUM – нөлге тең болатын бүтін сандардың бос емес ішкі жиынтығын табу (немесе мұндай ішкі жиын болмаса, бос жиынтықты қайтару) проблемасы. Бұл оптимизациялық проблема SUBSET SUM (ішкі жиынның қосындысы) шешімдік проблемасына ұқсас. Бүтін сандар жиынтығы берілгенде, SUBSET SUM – нөлге тең болатын ішкі жиынның бар-жоғын табу проблемасы. SUBSET SUM NP толық. FIND SUBSET SUM NP эквивалентті екенін көрсету үшін, оның NP қиын және NP оңай екенін көрсетуіміз керек. Оның NP қиын екені анық. Егер бізде бірлік уақытта FIND SUBSET SUM-ды шешетін «қара жәшік» болса, SUBSET SUM-ды шешу оңай болар еді. «Қара жәшіктен» нөлге тең келетін ішкі жиынды табуды сұраңыз, содан кейін ол бос емес жиынтықты қайтарды ма, жоқ па, тексеріңіз. Ол сондай-ақ NP оңай. Егер бізде SUBSET SUM-ды бірлік уақытта шешетін «қара жәшік» болса, оны FIND SUBSET SUM-ды шешу үшін пайдалануға болады. Егер ол false (жалған) қайтарса, біз бірден бос жиынтықты қайтарамыз. Әйтпесе, әр элементті ретімен қарап шығып, оны алып тастаймыз, егер SUBSET SUM оны алып тастағаннан кейін де true (ақиқат) қайтаратын болса. Барлық элементтерді қарап шыққаннан кейін, жауабын ақиқаттан жалғанға өзгертетін элементті алып тастай алмаймыз; осы сәтте бастапқы элементтердің қалған ішкі жиынтығы нөлге тең болуы керек. Бұл бізге элементтерді кейіннен алып тастаудың, ертерек элементті алып тастау жауабын ақиқаттан жалғанға өзгертетінін өзгертпейтінін ескеруді талап етеді. Псевдокодта:

функция FIND SUBSET SUM(жиын S)
егер SUBSET SUM(S) болмаса
{} қайтар
әр x үшін S-де
егер SUBSET SUM(S – {x}) болса
S := S – {x}
S қайтар

Тағы бір жақсы белгілі NP эквивалентті проблемасы – саяхатшы сатушысының (traveling salesman) проблемасы.

Түсіндірме

Осы контексте NP — детерминистік емес полиномиалдық уақытты білдіреді. Бульдік функциялардың NP эквиваленттік кластары да бар, онда NP — терістеу және алмастыруды білдіреді.