Кіріспе

Күрделілік класы
Есептеу күрделілігі теориясында FNP күрделілік класы – NP шешім класының функциялық проблемаға кеңейтілген түрі болып табылады. Атауы толыққанды дұрыс емес, себебі техникалық тұрғыдан алғанда, бұл функциялар емес, екілік қатынастар класы, және келесі ресми анықтама оны түсіндіреді:

Екілік қатынас P(x, y), мұнда y, x-тен полиномдық дәрежеде ғана ұзын, FNP-ге жатады, егер және тек егер детерминистік полиномдық уақыт алгоритмі P(x, y) қатынасының x және y үшін орындалатынын анықтай алса. Бұл анықтама нон-детерминизмді қамтымайды және NP-нің тексеруші анықтамасына ұқсас. Кез келген FNP қатынасына тікелей сәйкес келетін NP тілі бар, оны кейде аталған FNP қатынасынан туындаған немесе оған сәйкес келетін шешім проблемасы деп атайды. Бұл тіл P(x, y) қатынасы орындалатын барлық x-тің жиынтығы арқылы құрастырылады, бірақ белгілі бір шешім проблемасы үшін бірнеше FNP қатынастары болуы мүмкін. NP-дегі көптеген проблемалар, соның ішінде көптеген NP-толық проблемалар, белгілі бір нысанның бар-жоғын сұрайды, мысалы, қанағаттандыратын тапсырма, графты бояу немесе белгілі бір өлшемдегі клика. Осы проблемалардың FNP нұсқалары нысанның бар-жоғын ғана емес, егер ол бар болса, оның мәнін де сұрайды. Бұл әрбір NP-толық проблеманың FNP нұсқасы NP-қиын дегенді білдіреді. Белларе мен Голдвассер 1994 жылы кейбір стандартты болжамдарды қолданып, NP-де олардың FNP нұсқалары өзін-өзі қысқарта алмайтын проблемалар бар екенін көрсетті, яғни олардың сәйкес шешім проблемаларынан қиын екенін білдіреді. FNP-дегі әрбір P(x, y) үшін P(x, y) қатынасымен байланысты іздеу мәселесі: x берілген болса, P(x, y) орындалатын y табу немесе мұндай y жоқ екенін көрсету. FNP-дегі кез келген қатынасқа байланысты іздеу мәселесі полиномдық уақытта шешіледі, егер және тек егер P = NP болса. Бұл нәтиже әдетте "FP = FNP егер және тек егер P = NP болса" деп тұжырымдалады; алайда, бұл тұжырымның дұрыс болуы үшін FP және FNP мүшелерін қатынастар емес, керісінше қатынастарға байланысты іздеу проблемалары ретінде қайта анықтау қажет.

Қатысушы күрделілік сыныптары

FP – екілік қатынастар жиыны, онда x берілгенде P(x, y) шарты орындалатын y-ті табуға полиномиалдық уақыт алгоритмі бар. ФНП мен ФП арасындағы қатынас, NP мен P арасындағы қатынасқа ұқсас. TFNP – ФНП-ның ішкі жиыны: ол ФНП-дағы барлық x үшін кем дегенде бір y бар, онда P(x, y) орындалады.