Računska teorija složenosti

Kao grana teorije računanja u računarstvu, **računska teorija složenosti** opisuje skalabilnost algoritama, te inherentnu teškoću u pružanju skalabilnih algoritama za specifične računske probleme. To jest, teorija odgovara na pitanje, "Kako se veličina ulaza algoritma povećava, kako se mijenjaju vrijeme izvršavanja i memorijski zahtijevi algoritma?". Teorija određuje praktične granice na ono što računala mogu obaviti.

Implikacije teorije su važne vladi i industriji. Brzina i memorijski kapacitet računala uvijek rastu, baš kao i veličine skupova podatka koje treba analizirati. Ako algoritam ne uspije skalirati, tada će velika poboljšanja u računarskoj tehnologiji rezultirati tek u marginalnim povećanjima u praktičnim skupovima podataka.

Algoritmi i problemi su kategorizirani u klase složenosti. Najvažnije otvoreno pitanje teorije složenosti jest pitanje istovjetnosti klase ''P'' i klase ''NP'', odnosno je li prva podskup druge kao što se općenito smatra. Daleko od toga da se radi o ezoteričnoj vježbi - ubrzo nakon što je pitanje prvi put postavljeno, shvatilo se da su mnogi važni industrijski problemi u polju operacijskih istraživanja potklasa od *NP* zvana NP-potpuni problemi. NP-potpuni problemi imaju svojstvo da im se rješenja mogu brzo provjeriti, s tim da trenutne metode pronalaženja problema nisu skalabilne. Ako je klasa *NP* veća od *P*, tada ne postoji nijedno skalabilno rješenje za ove probleme. Je li to uistinu tako, je jedno od važnih otvorenih pitanja u računskoj teoriji složenosti.

## Pregled

Teorija se složenosti bavi relativnom računskom teškoćom izračunljivih funkcija. Ovo se razlikuje od teorije izračunljivosti, koja se bavi općenitim pitanjem može li se problem riješiti, bez obzira na zahtijevane resurse.

Jedan "problem" je jedinstven skup povezanih pitanja, pri čemu je svako pitanje string konačne duljine. Na primjer, problem ''FAKTORIZIRAJ'' jest: za dani cijeli broj zapisan u binarnom sustavu, vrati sve proste faktore tog broja. Pojedinačno se pitanje zove *instancom*. Na primjer, "daj faktore broja 15" je instanca problema *FAKTORIZIRAJ*.

**Vremenska složenost** problema je broj koraka potreban da bi se instanca problema riješila kao funkcija veličine ulaza (obično mjerenog u bitovima) koristeći najučinkovitiji algoritam. Da bi se ovo intuitivno razumjelo, može se razmotriti primjer instance duljine *n* bitova koja može biti riješena u *n*² koraka. U ovom primjeru kažemo da je problem vremenske složenosti *n*². Naravno, točan će broj koraka ovisiti o korištenom stroju. Kako bi se izbjegao taj problem, koristi se veliko O notacija. Ako problem ima vremensku složenost O(*n*²) na jednom tipičnom računalu, tada će također imati složenost O(*n*²) na većini drugih računala, tako da nam ova notacija omogućava poopćavanje detalja pojedinačnog računala.

**Primjer:** Košenje trave ima linearnu vremensku složenost s obzirom da treba dvostruko više vremena kako bi se kosilo dvostruko veće područje. Međutim, binarno pretraživanje rječnika ima svega logaritamsku vremensku složenost budući da dvostruko veći rječnik treba biti otvoren tek jedan put više (npr. točno u sredini - tada se veličina problema smanji za pola).

**Prostorna složenost** problema je povezan koncept, koji mjeri količinu prostora, ili memorije koju algoritam zahtijeva. Neformalna bi analogija bila količina papira korištenog za skiciranje prilikom rješavanja problema olovkom i papirom. Prostorna se složenost također mjeri velikom O notacijom.

Različita mjera složenosti problema, korisna u nekim slučajevima, jest **[[složenost sklopa]]**. Ovo je mjera veličine bulovskog sklopa potrebnog za računanje rješenja problema, u terminima broja logičkih vrata zahtijevanih za izgradnju sklopa. Takva je mjera korisna, na primjer, prilikom izgradnje sklopovskih mikročipova za izračunavanje funkcije, radije nego programske podrške.

## Problemi odluke
Veći se dio teorije složenosti bavi problemima odluke. Problem odluke je problem koji uvijek ima odgovor *da* ili *ne*. Teorija složenosti razlikuje probleme koji verificiraju odgovore *da* i one koji verificiraju odgovore *ne*. Problem koji invertira *da* i *ne* odgovore drugog problema se zove komplement tog problema.

Na primjer, poznati problem odluke *IS-PRIME* vraća odgovor *da* kad je dani ulaz prost, a inače *ne* odgovor, dok problem *IS-COMPOSITE* određuje *nije* li dani cijeli broj prost broj (tj. složen broj). Kad *IS-PRIME* vrati *da*, *IS-COMPOSITE* vraća *ne* i obrnuto. Stoga je *IS-COMPOSITE* komplement problema *IS-PRIME*, baš kao što je i *IS-PRIME* komplement problema *IS-COMPOSITE*.

Problemi se odluke često razmatraju budući da proizvoljan problem može uvijek biti sveden na problem odluke. Na primjer, problem *HAS-FACTOR* jest: za dane cijele brojeve *n* i *k* napisane u binarnom sustavu, vrati ima li *n* neke proste faktore manje od *k*. Ako problem *HAS-FACTOR* možemo riješiti korištenjem određene količine resursa, tada možemo to rješenje iskoristiti za rješavanje problema *FACTORIZE* bez mnogo dodatnih resursa. Ovo se može ostvariti binarnim pretraživanjem na *k* sve dok nije pronađen najmanji faktor od *n*, te potom dijeleći tim faktorom i opetujući postupak sve dok svi prosti faktori nisu nađeni.

Važan rezultat teorije složenosti jest činjenica da bez obzira koliko težak problem može postati (tj. koliko vremenskih i prostornih resursa zahtijeva), uvijek će postojati teži problemi. Za vremensku složenost, ovo se dokazuje teoremom o vremenskoj hijerarhiji. Na sličan način može biti izveden teorem o prostornoj hijerarhiji.

## Računski resursi

Teorija složenosti analizira teškoću računskih problema u terminima mnogo različitih računskih resursa. Isti se problem može opisati u terminima potrebnih količina raznih računskih resursa, uključujući vrijeme, prostor, slučajnost, alternaciju i ostale nešto manje intuitivne mjere. Klasa složenosti je skup svih računskih problema koji mogu biti riješeni koristeći određenu količinu određenog računskog resursa.

Jedni od najviše proučavanih računskih resursa su **[[determinističko vrijeme]]** (DTIME) i **[[deterministički prostor]]** (DSPACE). Ovi resursi predstavljaju količinu *vremena računanja* i *memorijskog prostora* potrebnih determinističkom računalu, poput onih stvarno postojećih. Ovi su resursi od velikog praktičnog interesa, i naširoko proučavani.

Neke je računske probleme lakše analizirati u terminima neobičnijih resursa. Na primjer, nedeterministički Turingov stroj je računski model kojem je dozvoljeno grananje kako bi odjednom ispitao mnogo različitih mogućnosti. Nedeterministički Turingov stroj nema mnogo veze sa stvarim fizičkim načinom na koji želimo izračunavati algoritme, ali njegovo grananje točno odgovara mnogim matematičkim modelima koje želimo analizirati, tako da je nedeterminističko vrijeme vrlo važan resurs u analiziranju računskih problema.

Mnogi, još neobičniji računski modeli se koriste u teoriji složenosti. Tehnički, bilo koja se mjera složenosti može shvatiti kao računski resurs, i mjere su složenosti vrlo široko definirane Blumovim aksiomima složenosti.

## Klase složenosti

Klasa složenosti je skup svih računskih problema koji se mogu riješiti koristeći određenu količinu određenog računskog resursa.

Klasa složenosti ''P'' je skup svih problema odluke koji mogu biti riješeni determinističkim Turingovim strojem u polinomnom vremenu. Ova klasa odgovara intuitivnoj ideji problema koji mogu biti učinkovito riješeni u najgorim slučajevima.

Klasa složenosti ''NP'' je skup problema odluke koji mogu biti riješeni nedeterminističkim Turingovim strojem u polinomnom vremenu. Ova klasa sadrži mnoge probleme koje bi ljudi željeli učinkovito riješiti, uključujući problem bulovske ispunjivosti, problem hamiltonovskog puta i problem prekrivanja vrhova. Svi problemi u ovoj klasi imaju svojstvo da im se rješenja mogu učinkovito provjeriti.

Mnoge se klase složenosti mogu karakterizirati u terminima matemtičke logike potrebnih da bi se izrazili - ovo se polje zove deskriptivna složenost.

## Otvorena pitanja
### PNP pitanje

Pitanje istovjetnosti skupova *NP* i *P* (tj. mogu li problemi koji mogu biti riješeni u *nedeterminističkom* polinomnom vremenu riješeni u *determinističkom* polinomnom vremenu) je jedno od najvažnijih otvorenih pitanja u teoretskom računarstvu, s obzirom na široke implikacije koje bi rješenje tog pitanja imalo.. Jedna negativna posljedica je ta da bi se mnogi oblici kriptografije mogli jednostavno "razbiti" i stoga postali beskorisni. Međutim, postojale bi i ogromne pozitivne posljedice, budući da bi mnogi važni problemi imali učinkovita rješenja. Takvi problemi uključuju razne tipove cjelobrojnog programiranja u operacijskim istraživanjima, mnoge probleme u logistici, predviđanju strukture bjelančevina u biologiji, te sposobnosti učinkovitog pronalaženja formalnih dokaza teorema u čistoj matematici korištenjem računala. *[[Clay Mathematics Institute]]* je 2000. obavio da će isplatiti nagradu od USD$ 1 000 000 prvoj osobi koja dokaže rješenje.

Pitanja poput ovih motiviraju koncepte *težine* i *[[potpun (složenost)|potpunosti]]*. Skup problema *X* je težak za skup problema *Y* ako svaki problem u *Y* može "lako" biti transformiran u neki problem u *X* koji producira rješenje. Definicija "lakog" je različita u različitim kontekstima. Važan *teški* skup u teoriji složenosti jest NP-težak - skup problema koji nisu nužno sami u *NP*, ali na koje bilo koji *NP* problem može biti sveden u polinomnom vremenu.

Skup *X* je potpun za *Y* ako je težak za *Y*, ali je također i podskup od *Y*. Važan potpun skup u teoriji složenosti je NP-potpun skup. Ovaj skup sadrži "najteže" probleme u NP, u smislu da su to oni koji najizglednije nisu u P. Zbog činjenice da problem *P**NP* ostaje neriješen, svođenje bi problema na poznati NP-potpun problem indiciralo da ne postoji poznato vremenski polinomno rješenje za njega. Slično, budući da svi *NP* problemi mogu biti svedeni na skup, pronalaženje *NP-potpunog* problema koji bi mogao biti riješen u polinomnom vremenu bi značilo *P**NP*.

### Nepotpuni problemi u ''NP''

Drugo otvoreno pitanje vezano za problem *P**NP* jest postoje li problemi koji su u NP, ali ne i u P, koji nisu NP-potpuni. Drugim riječima, problemi koji trebaju biti riješeni u nedeterminističkom polinomnom vremenu, ali ne mogu biti svedeni na polinomno vrijeme iz drugih nedeterminističkih vremenski polinomnih problema. Jedan takav problem, za koji se zna da je NP ali ne i da je NP-potpun, jest problem izomorfizma grafa - problem koji pokušava odlučiti jesu li dva grafa izomorfna (tj. dijele li ista svojstva). Pokazano je da ako vrijedi *P**NP*, da takvi problemi postoje.

### ''NP''''co-NP''
Gdje je co-NP skup koji sadrži komplementarne probleme (tj. problem sa invertiranim *da*/*ne* odgovorima) NP problema. Vjeruje se da te dvije klase nisu jednake, iako to dosad nije dokazano. Pokazano je da ako ove dvije klase nisu jednake, da tada slijedi da nijedan NP-potpun problem ne može biti u co-NP i nijedan co-NP-potpun problem ne može biti u NP.

## Neukrotivost
Problemi koji su rješivi u teoriji, ali ne mogu biti riješeni u praksi, se zovu *neukrotivima* (engl. *intractable*). Što točno može biti riješeno "u praksi" je otvoreno za diskusiju, ali općenito su samo problemi koji imaju vremenski polinomna rješenja rješivi za više od najmanjih ulaza. Problemi za koje se zna da su neukrotivi uključuju one koji su EXPTIME-potpuni. Ako NP nije isti kao i P, tada su NP-potpuni problemi također neukrotivi.

Da bi se vidjelo zašto rješenja u eksponencijalnom vremenu nisu uporabljiva u praksi, neka se razmotri problem koji zahtijeva 2n operacija za rješavanje (*n* je veličina ulaza). Za relativno male ulaze od n=100, i pretpostavljajući računalo koje može obaviti 1012 operacija u sekundi, rješenje bi zahtijevalo 4*1010 godina, mnogo više od trenutne starosti svemira.

## Istaknuti istraživači
* Laszlo Babai
* Manuel Blum, koji je razvio aksiomatsku teoriju složenosti zasnovanu na Blumovim aksiomima
* Allan Borodin
* Stephen Cook
* Uriel Feige
* Michael R. Garey
* Oded Goldreich
* Juris Hartmanis
* Johan Håstad
* Russell Impagliazzo
* David S. Johnson
* Richard Karp
* Marek Karpinski
* Leonid Levin
* Jack Lutz
* Christos H. Papadimitriou
* Alexander Razborov
* Steven Rudich
* Walter Savitch
* Adi Shamir
* Michael Sipser
* Richard Stearns
* Madhu Sudan
* Leslie Valiant
* Andrew Yao

## Povezano
* Složenost
* Popis tema u izračunljivosti i složenosti
* Složenost igara
* Složenost pjesama

## Izvori
* L. Fortnow, Steve Homer (2002./2003.). Kratka povijest računske složenosti. In D. van Dalen, J. Dawson, and A. Kanamori, urednici, *The History of Mathematical Logic*. North-Holland, Amsterdam.
* Jan van Leeuwen, ur. *Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity*, The MIT Press/Elsevier, 1990.  (Volume A). QA 76.H279 1990. Ogroman kompendij informacije, tisuće regerenci u različitim člancima.

## Vanjske veze

* The Complexity Zoo''  - wiki o klasama složenosti
* Besplatna knjiga o računskoj složenosti