Računski zadatak

U teorijskom računarstvu, računski problem je matematički objekat koji predstavlja zbirku pitanja koja bi računari mogli da reše. Na primer, problem faktorizacije

"Dat je pozitivan broj n, naći netrivijalni osnovni faktor od n."

je računski problem. Računski problemi su jedan od glavnih predmeta proučavanja teorijske računarske nauke. Oblast algoritama proučava metode efikasnog rešavanja računskih problema. Dopunsko polje računske kompleksnosti pokušava da objasni zašto su određeni računski problemi vezani za računare.

Matematički problem može da se posmatra kao beskonačno prikupljanje slučajeva zajedno sa rešenjem za svaki primer. Na primer, u problemu faktorizacije, instance su celi brojevi n i rešenja su prosti brojevi p koji opisuju netrivijalne proste faktore n.

To je uobičajeno da predstavi oba slučaja i rešenja od binarnih niski, odnosno elemenata {0, 1} *. Na primer, brojevi mogu biti predstavljeni kao binarne niske koristeći binarno kodiranje. (Zbog čitljivosti, identifikujemo brojeve sa njihovim binarnim kodiranjem u datim primerima.)

Vrste računskih zadataka

Problem odluke je računski problem gde je odgovor za svaki primer da ili ne. Primer problema odlučivanja je prosto testiranje:

"Dat je pozitivan broj n, odretiti da li je n prost."

Problem odluke se obično predstavlja kao skup svih slučajeva za koje je odgovor DA. Na primer, prosto testiranje može biti predstavljeno kao beskonačni skup

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

U problemu pretrage, odgovori mogu biti proizvoljne niske. Na primer, faktorizacija je problem pretrage gde su primeri (string predstave) pozitivni celi brojevi i rešenja su (string predstave) skupovi prostih brojeva.

Problem pretrage je predstavljen kao relacija koja se sastoji od svih instanci rešenja parova, naziva se relacija pretraživanja. Na primer, faktorizacija može biti predstavljena kao relacija

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

koja se sastoji od svih parova brojeva (n, p), gde je p netrivijalni glavni faktor n.

Problem brojanja pita za broj rešenja datog problema za pretraživanje. Na primer, problem brojanja povezan je sa faktorizacijom

"Dat je pozitivan broj n, izbrojati netrivijalne proste faktore n."

Problem brojanja može biti predstavljen preko funkcije f iz {0, 1} * na nenegativne cele brojeve. Za pretraga relacija R, problem brojanja povezan sa R je funkcija

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

Optimizacioni problem pita za pronalaženje "najboljeg mogućeg rešenja" među skupovima svih mogućih rešenja za problem pretraživanja. Jedan od primera je maksimalno nezavisan skup problema:

"Dat je grafik G, naći nezavisan skup od G maksimalne veličine"

Problemi optimizacije mogu se predstaviti svojim odnosima pretraživača.

U funkcijskom zadatku jedan izlaz (od ukupnog broja funkcija) očekuje se za svaki ulaz, ali izlaz je složeniji nego problem odlučivanja, to jest, to nije samo "da" ili "ne". Jedan od najpoznatijih primera je problem trgovačkog putnika:

"Dat je spisak gradova i razdaljina između svakog para gradova, treba naći najkraći put da poseti svaki grad tačno jednom i vrati se na prvobitni grad."

To je NP-težak problem u kombinatornoj optimizaciji, važnoj u operacionim istraživanjima i teorijskoj računarskoj nauci.

Problem obećanja

U teoriji računske kompleksnosti, obično se implicitno pretpostavlja da bilo koji niz u {0, 1} * predstavlja instancu računarskog problema. Međutim, ponekad nisu sve žice {0, 1} * predstavlja valjane primere, a jedna određuje odgovarajući podskup {0, 1} * kao skup "važećih instanci". Računski problemi ovog tipa nazivaju se problemi obećanja.

U nastavku je primer (odluka) problema obećanja:

"Dat je graf G, utvrditi da li svaki nezavisni skup u G ima najveću veličinu 5, ili G ima nezavisan skup najmanje veličine 10."

Ovde su validni slučajevi oni grafikoni čija je maksimalna veličina nezavisnog skupa bila najviše 5 ili najmanje 10.

Problemi odluke obećanja su obično predstavljeni kao parovi disjunktnih podskupova (L_yes, L_no) of {0, 1}^*. Važeći primeri su  u L_yes ∪ L_no. L_yes i L_no oni predstavljaju primere čiji odgovor je da i ne.

Problemi obećanja igraju važnu ulogu u nekoliko oblasti računske kompleksnosti, uključujući i tvrdoće približavanja, ispitivanje imovine i interaktivne dokaze sistema.

Literatura

• 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”. Ur.: Gowers, Timothy; Barrow-Green, June; Leader, Imre. The Princeton Companion to Mathematics. Princeton University Press. str. 575–604. ISBN 978-0-691-11880-2. .