Функціональна проблема: відмінності між версіями

У [[Теорія складності обчислень|Теорії складності обчислень]] '''функціональною проблемою''' є [[обчислювальна складність]], де для кожного вводу очікується окремий випуск ([[Обчислювана функція|обчислюваної функції]]), але вихід більш складний, ніж у {{Нп|Проблеми рішення |рішеннях проблем |en|decision problem}}. Для функціональних проблем вихід не просто «так» або «ні».

Функціональна проблема <math>P</math> визначається як відношення <math>R(x,y)</math> над [[Рядок (бази даних)| рядком]] довільної [[абеткаАбетка (інформатика) | абетки]] <math>\Sigma</math>:

Зверніть увагу, що вищезазначену проблему '''FSAT''' можна вирішити, використовуючи лише поліноміально багато викликів до підпрограми, яка вирішує проблему ''' SAT ''': алгоритм спочатку може запитати, чи є формула <math>\varphi</math> робочою. Після цього алгоритм може встановити змінну <math> x_1 </math> на TRUE і попросити ще раз. Якщо результуюча формула все ще виконується, алгоритм зберігає значення <math>x_1 </math> до значення TRUE і продовжує фіксувати <math>x_2 </math>, в іншому випадку він вирішить, що <math>x_1 </math> має бути FALSE і продовжить. Таким чином, '''FSAT''' вирішується в поліноміальному часі, використовуючи [[Пророча машина|пророчу машину]] вирішувати '''SAT'''. Загалом, проблема в '''NP''' називається самозбуджуваною, якщо її функціональний варіант може бути вирішено в поліноміальний час, використовуючи оракул, що вирішує оригінальну проблему. Кожна '''[[NP-повна задача |NP-повнота ]]''' проблема є самознижуваною. Вважається, що завдання цільної факторизації не самознижується.

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

Функціональні проблеми можуть бути {{Нп|Зменшення |скорочені |en|Reducation (complexity) }} дуже схоже на вирішення проблем: задані функціональні проблеми <math>\Pi_R</math> та <math>\Pi_S</math> також <math>\Pi_R</math> зменшується до <math>\Pi_S</math> якщо існують поліномальні часи обчислювання функції <math>f</math> and <math>g</math> така, що для всіх випадків <math>x</math> of <math>R</math> та реальне рішення <math>y</math> з <math>S</math>, воно важаєтьсявважається

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

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