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 zahtjevi 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.
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 na to 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 jer 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
.
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 jer 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
.
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
.
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.
[1]
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.
[1]
Mnoge se klase slo?enosti mogu karakterizirati u terminima
matemti?ke logike
potrebnih da bi se izrazili - ovo se polje zove
deskriptivna slo?enost
.
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.
[1]
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, jer 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
.
[2]
[3]
Clay Mathematics Institute
je
2000.
obavio da ?e isplatiti nagradu od
USD$
1 000 000 prvoj osobi koja doka?e rje?enje.
[4]
Pitanja poput ovih motiviraju koncepte
te?ine
i
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, jer 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
.
[1]
Nepotpuni problemi u
NP
[
uredi
|
uredi kod
]
Dijagram klasa slo?enosti uz pretpostavku da vrijedi
P
≠
NP
. Postojanje problema izvan klasa i
P
i
NP
-potpun u ovom slu?aju je postavio Ladner.
[5]
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, v.
izomorfni graf
). Pokazano je da ako vrijedi
P
≠
NP
, da takvi problemi postoje.
[6]
Gdje je
co-NP
skup koji sadr?i
komplementarne
probleme (tj. problem s 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.
[6]
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 2
n
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 10
12
operacija u sekundi, rje?enje bi zahtijevalo 4*10
10
godina, mnogo vi?e od trenutne
starosti svemira
.
Istaknuti istra?iva?i
[
uredi
|
uredi kod
]
- 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.
ISBN
978-0-444-88071-0
(Volume A). QA 76.H279 1990. Ogroman kompendij informacije, tisu?e regerenci u razli?itim ?lancima.