Функціональна проблема

функціональною проблемою у теорії складності обчислень є обчислювальна складність, де для кожного введеного значення очікується окреме вихідне значення (обчислюваної функції), але воно більш складне, ніж у проблемі вибору. Для функціональних проблем вихідне значення зазвичай не просто «так» або «ні».

Формальне визначення

Функціональна проблема $P$ визначається як відношення $R(x,y)$ над рядком довільної абетки $\Sigma$: $R\subset \Sigma ^{*}\times \Sigma ^{*}$ Алгоритм вирішується $P$ якщо для кожного вводу $x$ такий, що існує a $y$ satisfying $(x,y)\in R$, алгоритм видає один такий $y$.

Приклади

Відома функціональна проблема — це функціональна здійсненність бульових формул, скорочено FSAT (англ. Functional Boolean Satisfiability Problem). Проблема, яка тісно пов'язана з задачею здійсненності бульових формул (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 — це сукупність функціональних завдань, які можна вирішити за допомогою недетермінованої машини Тюрінга у поліноміальному часі.

Самозалежність

Зверніть увагу, що вищезазначену проблему FSAT можна вирішити, використовуючи лише поліноміально багато викликів до підпрограми, яка вирішує проблему SAT: алгоритм спочатку може запитати, чи є формула $\varphi$ робочою. Після цього алгоритм може встановити змінну $x_{1}$ на TRUE і попросити ще раз. Якщо результуюча формула все ще виконується, алгоритм зберігає значення $x_{1}$ до значення TRUE і продовжує фіксувати $x_{2}$, в іншому випадку він вирішить, що $x_{1}$ має бути FALSE і продовжить. Таким чином, FSAT вирішується в поліноміальному часі, використовуючи пророчу машину вирішувати SAT. Загалом, проблема в NP називається самозбуджуваною, якщо її функціональний варіант може бути вирішено в поліноміальний час, використовуючи оракул, що вирішує оригінальну проблему. Кожна NP-повнота проблема є самознижуваною. Вважається, що завдання цільної факторизації не самознижується.

Зниження і повні проблеми

Функціональні проблеми можуть бути зведені дуже схоже на вирішення проблем: задані функціональні проблеми $\Pi _{R}$ та $\Pi _{S}$ також $\Pi _{R}$ зменшується до $\Pi _{S}$ якщо існують поліноміальні часи обчислювання функції $f$ and $g$ така, що для всіх випадків $x$ of $R$ та реальне рішення $y$ з $S$, воно вважається

• If $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$. Тому питання обчислюваності доказів не відділяється від питання про їх існування. Для подолання цієї проблеми зручно розглянути обмеження функціональних завдань на загальні відносини, що дають клас TFNP як підклас FNP. Цей клас містить такі проблеми, як розрахунок чистої рівноваги Неша у певних стратегічних іграх, де гарантовано існує рішення. Показано, що $\mathbf {(} TFNP)=\mathbf {(} F)(\mathbf {(} NP)\cap {\textbf {(}}co-NP))$. Крім того, якщо TFNP містить будь-яку проблему FNP-повноти, то $\mathbf {(} NP)={\textbf {co-NP}}$.

Див. також

• Алгоритм пошуку
• Оптимізація
• Підрахунок посилань
• Проблема вибору

Література

• Raymond Greenlaw, H. James Hoover, «Основи теорії обчислень: принципи та практика», Morgan Kaufmann, 1998, p. 45-51, ISBN 1-55860-474-X
• Elaine Rich, Автомати, обчислюваність і складність: теорія та додатки, Prentice Hall, 2008, розділ 28.10 «Проблемні класи FP і FNP», с. 689—694, ISBN 0-13-228806-0