Кіріспе

Есептеу проблемасының түрі
Есептеу күрделілігі теориясында, функциялық проблема – әрбір кіріс үшін жалпы функцияның бір ғана шығысы күтілетін, бірақ шығысы шешім проблемасынан гөрі күрделі есептеу проблемасы. Функциялық проблемалар үшін шығыс жауабы тек "иә" немесе "жоқ" бола бермейді.

Мысалдар

Жақсы белгілі бір функциялық мәселе Функционалдық Бульдық Қанағаттандыру Мәселесі (FSAT) арқылы беріледі. Бұл мәселе SAT шешім мәселесімен тығыз байланысты және былай тұжырымдалады:

Берілген буль формуласы , айнымалылары бар , формуланың мәнін True-ға тең ететін тапсырманы табыңыз немесе мұндай тапсырманың жоқтығын анықтаңыз. Бұл жағдайда қатынас тиісті түрде кодталған буль формулалары мен оларды қанағаттандыратын тапсырмалар жұптары арқылы беріледі. SAT алгоритмі формуламен жұмыс істегенде тек "қанағаттандырылмайды" немесе "қанағаттандырылады" деп қайтару жеткілікті, ал FSAT алгоритмі соңғы жағдайда қанағаттандыратын тапсырманы қайтаруы керек. Басқа да маңызды мысалдарға саяхатшы сатушы мәселесі (сатушының бағытын табу) және бүтін санды жіктеу мәселесі (факторлар тізімін табу) жатады.

Басқа күрделілік сыныптарымен байланыс

NP класындағы кез келген шешім есепті қарастырайық. NP анықтамасы бойынша, "иә" деп жауап берілген әрбір есеп мысалы үшін "иә" жауабын дәлелдейтін полиномдық өлшемдегі куәлік бар. Осылайша, осы жұптардың жиыны қатынас құрайды, ол "берілген , үшін куәлік табу" функциялық есепті көрсетеді. Бұл функциялық есеп – функцияның функциялық түрі деп аталады; ол FNP класына жатады. FNP NP класындағы функциялық есептердің аналогы ретінде қарастырылуы мүмкін, себебі FNP есептерінің шешімдері тиімді түрде (яғни, кірістің ұзындығына қатысты полиномдық уақытта) тексеріле алады, бірақ міндетті түрде тиімді түрде табыла бермейді. Ал, P класындағы функциялық есептердің аналогы ретінде қарастырылатын FP класы, шешімдері полиномдық уақытта табылса болатын функциялық есептерден тұрады.

Өзін-өзі азайту

Жоғарыда келтірілген FSAT мәселесін SAT мәселесін шешетін процедураға полиномдық санда шақыру арқылы шешуге болады: Алгоритм бастапқыда формула қанағаттандырылатындығын сұрай алады. Содан кейін алгоритм айнымалыны TRUE деп бекітіп, қайтадан сұрай алады. Егер алынған формула әлі де қанағаттандырылатын болса, алгоритм оны TRUE деп бекітілген күйде қалдырып, бекітуді жалғастырады, әйтпесе ол FALSE болуы керек деп шешіп, жалғастырады. Осылайша, FSAT мәселесі SAT мәселесін шешетін оракул арқылы полиномдық уақытта шешіледі. Жалпы, егер мәселенің функциялық түрі бастапқы мәселені шешетін оракул арқылы полиномдық уақытта шешілсе, онда NP класындағы мәселе өзін-өзі келуге болатын деп аталады. Кез келген NP-толық мәселе өзін-өзі келуге болады. Бүтін санды факторлау мәселесі өзін-өзі келуге болмайды деп болжанады, себебі бүтін сан жай сан екенін анықтау P (оңай), ал бүтін санды факторлау мәселесі классикалық компьютер үшін қиын деп есептеледі. Өзін-өзі келудің бірнеше (сәл өзгеше) түсінігі бар.

Жалпы функциялық мәселелер

Функциялық мәселелерді анықтау үшін қолданылатын қатынастың бір кемшілігі – толық еместігі: әрбір кіріс үшін оған сәйкес келетін элемент табылмауы мүмкін. Сондықтан, дәлелдердің есептелу мүмкіндігі туралы мәселе олардың болуы туралы мәселеден ажыратылмайды. Бұл мәселені шешу үшін функциялық мәселелерді толық қатынастармен шектеу ыңғайлы, бұл TFNP класын FNP класының ішкі класы ретінде құрайды. Бұл класта белгілі бір стратегиялық ойындардағы таза Нэш тепе-теңдігін есептеу сияқты, шешімі бар екені кепілденген мәселелер бар. Сонымен қатар, егер TFNP класында FNP-толық мәселе болса, онда .