Ömür boyu gözlədiyiniz gün gəlib çatdı: Siz maksimal dəst məsələsini həll etmək üçün üsul kəşf etdiniz: istiqamətlənməmiş qraf verilir, dəst formalaşdıran qrafın təpə nöqtələrinin maksimal altçoxluğunu tapmaq lazımdır (bütün təpə nöqtələri cüt-cüt birləşdirilmişdir. Bu məsələ NP-çətinliklidir, lakin sizin əlinizdə isbat vardır ki, P = NP!
Təəssüf ki, elmi cəmiyyət Sizi heç eşitmək də istəmir. Sizin bu məsələ ilə bağlı sənədləriniz hazırki vaxtda qəbul edilməmişdir, ona görə ki, “həlli olmayan məsələnin həlli yoxdur”. Sizin telefon nömrəniz artıq tanıdığınız bütün kompüter elmləri professorlаrının ləğv etmə siyahsındadır. Dünya, belə çıxır ki, sizi görmək istəmir.
Onda siz maksimal dəstin tapılması məsələsinin həlli alqoritmini tərtib etmək və onu İnternetdə yerləşdirmək qərarına gəldiniz ki, hər bir kəs Sizin doğru olduğunuzu sərbəst yoxlaya bilsin. Siz artıq testləşdirici sistemi reallaşdırmısınız və bunun üçün demək olar ki, veb-saytı yükləmişiniz, lakin sonra Siz başa düşdünüz ki, bu elə də yaxşı ideya deyil. Əgər Siz həlledicinin əlyetərli olmasını təmin edərsinizsə, onda hər kəs NP-məsələlərini maksimal dəstin tapılmasına gətirərək həll edə bilər. Əgər insanlar Sizə məşhurluq və hörmət gətirilməsi üçün sadəcə Sizin kəşfinizi sakitcə istifadə edərlərsə, nə etməli?
Xoşbəxtlikdən Sizin bildiyiniz maksimal dəst haqqında məsələnin NP-mürəkkəbliyinin yeganə isbatı onun kifayət qədər spesifik üsulla 3-SAT məsələsinə çevirməkdən ibarətdir. Buna görə Siz yoxlamaq qərarına gəldiniz ki, o çevirmə nəticəsində Sizin həlləedici üçün giriş qrafı alındımı və əgər alındısa, onda Siz məsələnin həllindən imtina edəcəksiniz. Bu şəkildə heç kəs NP sinifli məsələlər üçün cəld həll tapa bilməyəcək, lakin hər bir kəs Sizin həlledicinizin girişinə başqa formada qraf verərək onun işini yoxlaya bilər.
3-SAT məsələsi növbəti şəkildə ifadə olunur: ,
şəklində düstur verilir, burada hər bir t^i_j terimi bul dəyişkəni və ya unun inkarıdır (daha formal olaraq ya x_k, ya da ¬x_k). Düsturun doğru olması üçün dəyişkənlərə qiymət verilməsinin mümkünlüyünü təyin etmək lazımdır. Mötərizədəki hər üç term müxtəlif dəyişkənləri təmsil etməlidir.
Cevirmə növbəti şəkildə işləyir. Cari düstura görə hər biri bir mötərizə dəyişkəninə uyğun gələn 3n təpə nöqtəli qraf quraq. t^i_j və t^r_s termlərinə uyğun gələn iki təpə nöqtəsi i ≠ r (termlər müxtəlif mötərizə ifadələrinə məxsusdur) olarsa, tillərlə birləşdirilir və termlər ziddiyətli deyildirlər (onlar ya eynidirlər, ya da müxtəlif dəyişkənləri təmsil edirlər).
Növbəti şəkildə (x_1∨x_2∨¬x_3)∧(¬x_1∨¬x_2∨x_4)∧(¬x_1∨¬x_2∨¬x_4) düsturu ilə alınan qraf təsvir olunmuşdur:
n-ölçülü dəst dəyişkən qiymətə doğru/yanlış qiymətinin elə mənimsədilməsinə uyğundur ki, hər bir mötərizə ifadəsində heç olmazsa bir dəyişkən doğru qiymətini alır. Şəkildə 3 ölçüsündə dəst təşkil edən tillər seçilmişdir. x_1–in yanlış və x_2–nin doğru qurulması x_3 və x_4 dəyişkənlərinin qiymətlərindən asılı olmayaraq bütün mötərizə ifadələrinin yerinə yetirilməsini təmin edir.
Verilmiş qrafa görə onun yuxarıda şərh edilən çevirməyə görə alınmasını mümkünlüyünü təyin etmək lazımdır. Təpə nöqtələri ixtiyari ardıcıllıqda verilə bilər.
Giriş faylının birinci sətrində qrafın təpə nöqtələrinin və tillərinin sayını ifadə edən iki v (1 ≤ v ≤ 100) və e tam ədədləri verilir. Hər bir növbəti e sətrdə tillə birləşdirilmiş təpə nöqtələrinin sayını ifadə edən iki tam ədəd verilir. Hər bir təpə nöqtəsi cütlüyü birdən çox olmayaraq birləşdirilib, heç bir til təpə nöqtəsini özü ilə birləşdirmir.
Göstərilən çevirmə nəticəsində verilmiş qrafı əldə etmək mümükün olarsa, "YES" və əks halda "NO" verməli.