Функцијски задатак

У теорији рачунарске комплексности, проблем функција је рачунски проблем где се очекује један излаз (од укупно броја функција) за сваки улаз, али излаз је сложенији него проблем одлуке, то јест, то није само ДА или НЕ.^[1]

Формална дефиниција

Функцијски проблем $P$ је дефинисан као релација $R(x,y)$ преко Декартовог производа над нискама произвољног алфабета $\Sigma$ :

$R\subset \Sigma ^{*}\times \Sigma ^{*}$

Алгоритам решава $P$ за сваки унос $x$ такав да постоји $y$ и да $(x,y)\in R$ буде задовољено, па алгоритам ствара неко $y$ .

Примери

Познат функцијски задатак дат је из Функцијског Булововог проблема задовољивости, FSAT скраћено. Проблем, који је уско повезан са доношењем проблема SAT може се формулисати на следећи начин:

Дата је Булова формула $\varphi$ са променљивим $x_{1},\ldots ,x_{n}$ , доделити $x_{i}\rightarrow \{{\text{TRUE}},{\text{FALSE}}\}$ тако да је $\varphi$ једнако ${\text{TRUE}}$ или нема додељивања.

У случају релације $R(x,y)$ дато је торки одговарајуће кодирање Булових формула и задовољавање задатака.

Остали значајни примери су проблем трговачког путника, који тражи за руте које су узете од продавца, и проблем растављања на факторе, који тражи листу фактора.

Однос према другим класама сложености

Размотрити произвољни проблем одлучивања у класи NP. По дефиницији сваки проблем инстанце $x$ где је одговорено са 'да' има потврду за $y$ која служи као доказ да је 'да' одговор. Скуп тих торки $(x,y)$ формира релацију. Сложеност класа изведена из ове трансформације је означен $\mathbf {F} (\mathbf {NP} )$ или FNP скраћено. Мапирање сложености класе P је означено као FP. Класа FP је скуп проблема у функционисању који се могу решити помоћу детерминистичке Тјурингове машине у субекспонценцијалном времену, док је FNP скуп проблема у функционисању који се могу решити од стране не-детерминистичке Тјурингове машине у субекспоненцијалном времену.^[2]

Самосвесност

Обратите пажњу да проблем FSAT који је уведен изнад и може бити решен коришћењем само субекспоценцијалних позива на потпрограме о којима одлучује SAT проблем: Алгоритам може прво питати да ли је формула $\varphi$ задовољива. Након тога алгоритам може да промени променљиву $x_{1}$ у ТАЧНО и пита поново. Ако је резултујућа формула задовољива, алгоритам $x_{1}$ преправља на ТАЧНО и наставља да преправи $x_{2}$ , иначе је одлучено да $x_{1}$ мора бити лажан и наставља даље. Дакле, FSAT је решив у субекспоненцијалном времену користећи пророчку машину о којој одлучује SAT. У принципу, проблем NP се зове самосвесни ако је његова функција у ствари варијанта која може бити решена у субекспоненцијалном времену користећи пророчку машину за одлучујући оригинални проблем. Сваки NP-комплетни проблем је самосвестан. Претпостављено је да проблем растављен на факторе није самосвестан.

Редукција и комплетни проблеми

Проблеми функција се могу редуковати слично проблемима доношења: Имајући у виду проблеме функције $\Pi _{R}$ и $\Pi _{S}$ кажемо да се $\Pi _{R}$ своди на $\Pi _{S}$ ако постоји полином времена функције $f$ and $g$ тако да за све случајеве $x$ of $R$ и могуће опције $y$ од $S$ , сматра се да

Ако $x$ има $R$ -опцију, онда $f(x)$ има $S$ -опцију.
$(f(x),y)\in S\implies (x,g(x,y))\in R.$

Стога је могуће дефинисати FNP-комплетне проблеме аналогне NP-комплетном проблему:

Проблем $\Pi _{R}$ је FNP-комплетан ако сваки проблем у FNPможе бити редукован у $\Pi _{R}$ . Комплексност класе FNP-комплетни проблеми су означени са FNP-C или FNPC. То се поклапа са $\mathbf {F} (\mathbf {NP} )$ . Одатле је проблем FSAT исто FNP-комплетан проблем, и то подразмева да је $\mathbf {P} =\mathbf {NP}$ ако и само ако је $\mathbf {FP} =\mathbf {FNP}$ .

Збир функцијских задатака

Релација $R(x,y)$ користи се за дефинисање проблема који могу да имају недостатак и да буду непотпуни: није сваки унос $x$ дупликат $y$ тако да $(x,y)\in R$ . Стога питање доказа није одвојено од питања његовог постојања. Да би се превазишао овај проблем згодно је размотрити ограничавање функције проблема до укупног односа класе ТFNP као подкласе од FNP. Ова класа садржи проблеме као што су израчунавања Нешовог еквилибријума у појединим стратешким играма где се гарантује да постоји решење. Онда је показано да $\mathbf {TFNP} =\mathbf {F} (\mathbf {NP} \cap {\textbf {co-NP}})$ . Поред тога, ако TFNP садржи NP-комплетне проблеме следи да је $\mathbf {NP} ={\textbf {co-NP}}$ .

Види још

Референце

^ Raymond Greenlaw; H. James Hoover (1998). Fundamentals of the theory of computation: principles and practice. Morgan Kaufmann. стр. 45-51. ISBN 978-1-55860-474-2.
^ Rich, Elaine (2008). „The problem classes FP and FNP”. Automata, computability and complexity: theory and applications. Prentice Hall. стр. 689-694. ISBN 978-0-13-228806-4.

[1] Raymond Greenlaw; H. James Hoover (1998). Fundamentals of the theory of computation: principles and practice. Morgan Kaufmann. стр. 45-51. ISBN 978-1-55860-474-2.

[2] Rich, Elaine (2008). „The problem classes FP and FNP”. Automata, computability and complexity: theory and applications. Prentice Hall. стр. 689-694. ISBN 978-0-13-228806-4.

[1]

[2]