Рачунски задатак

У теоријском рачунарству, рачунски проблем је математички објекат који представља збирку питања која би рачунари могли да реше.^[1] На пример, проблем факторизације

"Дат је позитиван број n, наћи нетривијални основни фактор од n."

је рачунски проблем. Рачунски проблеми су један од главних предмета проучавања теоријске рачунарске науке. Област алгоритама проучава методе ефикасног решавања рачунских проблема. Допунско поље рачунске комплексности покушава да објасни зашто су одређени рачунски проблеми везани за рачунаре.

Математички проблем може да се посматра као бесконачно прикупљање случајева заједно са решењем за сваки пример. На пример, у проблему факторизације, инстанце су цели бројеви n и решења су прости бројеви p који описују нетривијалне просте факторе n.

То је уобичајено да представи оба случаја и решења од бинарних ниски, односно елемената {0, 1} *. На пример, бројеви могу бити представљени као бинарне ниске користећи бинарно кодирање. (Због читљивости, идентификујемо бројеве са њиховим бинарним кодирањем у датим примерима.)

Врсте рачунских задатака

Проблем одлуке је рачунски проблем где је одговор за сваки пример да или не. Пример проблема одлучивања је просто тестирање:

"Дат је позитиван број n, одретити да ли је n прост."

Проблем одлуке се обично представља као скуп свих случајева за које је одговор ДА. На пример, просто тестирање може бити представљено као бесконачни скуп

L = {2, 3, 5, 7, 11, ...}

У проблему претраге, одговори могу бити произвољне ниске. На пример, факторизација је проблем претраге где су примери (стринг представе) позитивни цели бројеви и решења су (стринг представе) скупови простих бројева.

Проблем претраге је представљен као релација која се састоји од свих инстанци решења парова, назива се релација претраживања. На пример, факторизација може бити представљена као релација

R = {(4, 2), (6, 2), (6, 3), (8, 2), (9, 3), (10, 2), (10, 5)...}

која се састоји од свих парова бројева (n, p), где је p нетривијални главни фактор n.

Проблем бројања пита за број решења датог проблема за претраживање. На пример, проблем бројања повезан је са факторизацијом

"Дат је позитиван број n, избројати нетривијалне просте факторе n."

Проблем бројања може бити представљен преко функције f из {0, 1} * на ненегативне целе бројеве. За претрага релација R, проблем бројања повезан са R је функција

f_R(x) = |{y: R(x, y) }|.

Оптимизациони проблем пита за проналажење "најбољег могућег решења" међу скуповима свих могућих решења за проблем претраживања. Један од примера је максимално независан скуп проблема:

"Дат је график G, наћи независан скуп од G максималне величине"

Проблеми оптимизације могу се представити својим односима претраживача.

У функцијском задатку један излаз (од укупног броја функција) очекује се за сваки улаз, али излаз је сложенији него проблем одлучивања, то јест, то није само "да" или "не". Један од најпознатијих примера је проблем трговачког путника:

"Дат је списак градова и раздаљина између сваког пара градова, треба наћи најкраћи пут да посети сваки град тачно једном и врати се на првобитни град."

То је НП-тежак проблем у комбинаторној оптимизацији, важној у операционим истраживањима и теоријској рачунарској науци.

Проблем обећања

У теорији рачунске комплексности, обично се имплицитно претпоставља да било који низ у {0, 1} * представља инстанцу рачунарског проблема. Међутим, понекад нису све жице {0, 1} * представља ваљане примере, а једна одређује одговарајући подскуп {0, 1} * као скуп "важећих инстанци". Рачунски проблеми овог типа називају се проблеми обећања.

У наставку је пример (одлука) проблема обећања:

"Дат је граф G, утврдити да ли сваки независни скуп у G има највећу величину 5, или G има независан скуп најмање величине 10."

Овде су валидни случајеви они графикони чија је максимална величина независног скупа била највише 5 или најмање 10.

Проблеми одлуке обећања су обично представљени као парови дисјунктних подскупова (L_yes, L_no) of {0, 1}^*. Важећи примери су у L_yes ∪ L_no. L_yes и L_no они представљају примере чији одговор је да и не.

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

Референце

^ Even, Shimon; Selman, Alan L.; Yacobi, Yacov (1984), „The complexity of promise problems with applications to public-key cryptography”, Information and Control, 61 (2): 159—173, doi:10.1016/S0019-9958(84)80056-X .

Литература

Goldreich, Oded (2008). Computational Complexity: A Conceptual Perspective. Cambridge University Press. ISBN 978-0-521-88473-0. .
Goldreich, Oded; Wigderson, Avi (2008). „IV.20 Computational Complexity”. Ур.: Gowers, Timothy; Barrow-Green, June; Leader, Imre. The Princeton Companion to Mathematics. Princeton University Press. стр. 575–604. ISBN 978-0-691-11880-2. .

[1] Even, Shimon; Selman, Alan L.; Yacobi, Yacov (1984), „The complexity of promise problems with applications to public-key cryptography”, Information and Control, 61 (2): 159—173, doi:10.1016/S0019-9958(84)80056-X .

[1]