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

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

Відома функціональна проблема — це функціональна здійсненність бульових формул, скорочено FSAT (англ. Functional Boolean Satisfiability Problem). Проблема, яка тісно пов'язана з задачею здійсненності бульових формул (SAT), може бути сформульована таким чином: Дана логічна формула ${\displaystyle \varphi }$ від змінних ${\displaystyle x_{1},\ldots ,x_{n}}$, знайти значення ${\displaystyle x_{i}\rightarrow \{{\text{TRUE}},{\text{FALSE}}\}}$ таке як ${\displaystyle \varphi }$ оцінюється до ${\displaystyle {\text{TRUE}}}$ або вирішити, що такого значення не існує. У цьому випадку співвідношення ${\displaystyle R(x,y)}$ дається кортежами правильно закодованих логічних формул і задовольняє призначенням. Інші помітні приклади включають проблему з задачі комівояжера, в якій пропонується маршрут продавця та проблема факторізації цілого числа яка вимагає списку множників.

Розглянемо довільну проблему вибору у класі NP. За визначенням кожна проблема екземпляра ${\displaystyle x}$ які мають відповідь «так», мають засвідчувати ${\displaystyle y}$ який служить доказом відповіді «так». Таким чином, набір цих кортежів ${\displaystyle (x,y)}$ утворює відношення. Клас складності, отриманий з цього перетворення, позначається через ${\displaystyle \mathbf {F} (\mathbf {NP} )}$ або FNP якщо скорочено. Відображення класу складності P означає FP. Клас FP — це сукупність функціональних завдань, які можна вирішити за допомогою машини Тюрінга у поліноміальному часі, в той час як FNP — це сукупність функціональних завдань, які можна вирішити за допомогою недетермінованої машини Тюрінга у поліноміальному часі.

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

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

• If ${\displaystyle x}$ має ${\displaystyle R}$-рішення, після ${\displaystyle f(x)}$ має ${\displaystyle S}$-рішення.
• ${\displaystyle (f(x),y)\in S\implies (x,g(x,y))\in R.}$

Тому можна визначити FNP-повнота проблеми, аналогічні NP-повної задачі: Проблема ${\displaystyle \ Pi_{R}}$ є FNP-повнота, якщо кожну проблему в FNP можна звести до ${\displaystyle \ Pi_{R}}$. Клас складності проблем FNP-повний позначається як FNP-C або FNPC . Це збігається з ${\displaystyle \mathbf {(} F)(\mathbf {(} NP))}$. Отже, проблема FSAT також є проблемою FNP-повноти, і вона вважає, що ${\displaystyle \mathbf {(} P)=\mathbf {(} NP)}$ тоді і тільки тоді, коли ${\displaystyle \mathbf {(} FP)=\mathbf {(} FNP)}$.

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