Класа сложености

У теорији рачунарске сложености, класа сложености је скуп проблема повезаних ресурсима заснованим на сложености. Типична сложеност класа има дефиницију облика:

скуп проблема који се могу решити апстрактном машином М коришћењем O(f(n)) ресурса Р, где је n величина улаза.

Сложене класе су забринуте са стопом раста захтева за ресурсе као и повећавање улаза n. То је апстрактно мерење, и не даје време или простор у секунди или бајту, што захтева познавање имплементације специфичности. Функција унутар O(...) израза може бити константа, за алгоритме који су под утицајем величине n, или израза који садржи логаритам, израз укључује n, односно полиномни израз, и многе друге. O се чита као "редослед...". За потребе израчунавања теорије сложености, неке од детаља функције се могу занемарити, на пример много могућих полинома може бити груписано као класа.

Питање ресурса може бити или време, у суштии број примитивних операција на апстрактне машине, или (за складиштење) простор. На пример, класа NP је скуп свих проблема одлучивања који могу бити решени недетерминистичком Тјуринговом машином у полиномијалном времену док је класа PSPACE скуп свих проблема одлуке који могу бити решени детерминистичком Тјуринговом машином у полиномијалном простору.

Најједноставније класе сложености су дефинисане следећим факторима:

• Тип рачунарских проблема: Најчешће коришћени проблеми су проблеми одлучивања. Међутим, класе сложености се могу дефинисати на основу функцијских проблема (пример је FP), рачунарских проблема (нпр.#P), оптимизационих проблема, обећавајућих проблема итд...
• Модел рачунања: Најчешћи модел рачунања је детерминистичка Тјурингова машина, али многе класе сложености су засноване на недетерминистичким Тјуринговим машинама, логички склоп, квантна Тјурингова машина, монотон склоп, итд.
• Ресурс(или ресурси) који се граниче и границе: Ове две особине се обично наводе заједно, као што су "полиномијално време", "логаритамски простор", "константна дубина", итд.

Многе класе сложености се могу окарактерисати као математичка логика која жели да их изрази;

Гранично време израчунавања неке конкретне фукнције f(n) чсто даје сложеност класе која зависи од изабраног модела машине. На пример, језик {xx | x је било који бинарни ниѕ} може да е реши у линеарном ремену на мулти-траци Тјурингове машине, али нужно захтева квадратно време у моделу једне-траке Тјурингове машине. Ако дозволимо полиномијалну варијацију у текућем времену, Cobham-Edmonds теза гласи да је "временска сложеност било која два разумна и општа модела обрачуна су полиномијално везана". Ово представља основу за сложеност класе P, која је низ датих проблема одлуке решена детерминистичком Тјуринговом машином у полиномијалном времену одговарајућег скупа функцијиских проблема је FP.

Блумове аксиоме се могу користити за дефинисање класа сложености без позивања на неки конкретни рачунски модел.

Важне класе сложености

Многе важне класе сложености могу бити дефинисане помоћу граница времена или простора које користи алгоритам. Неке важне класе сложености доношења проблема дефинисане су на следећи начин:

Класа сложености	Модел рачунања	Ограничење ресурса
DTIME (f(n))	Детерминистичка Тјурингова машина	Време f(n)
P	Детерминистичка Тјурингова машина	Полиномијално време
EXPTIME	Детерминистичка Тјурингова машина	Време 2полиномијално(n)
NTIME(f(n))	Недетерминистичка Тјурингова машина	Време f(n)
NP	Недетерминистичка Тјурингова машина	Полиномијално време
NEXPTIME	Недетерминистичка Тјурингова машина	Време 2полиномијално(n)
DSPACE(f(n))	Детерминистичка Тјурингова машина	Простор f(n)
L	Детерминистичка Тјурингова машина	Простор O(logn)
PSPACE	Детерминистичка Тјурингова машина	Полиномијални простор (n)
EXPSPACE	Детерминистичка Тјурингова машина	Простор 2полиномијално(n)
NSPACE(f(n))	Недетерминистичка Тјурингова машина	Простор f(n)
NL	Недетерминистичка Тјурингова машина	Простор O(logn)
NPSPACE	Недетерминистичка Тјурингова машина	Полиномијални простор (n)
NEXPSPACE	Недетерминистичка Тјурингова машина	Простор 2полиномијално(n)

Испоставило се да PSPACE = NPSPACE и EXPSPACE = NEXPSPACE .

Друге важне класе сложености укључују BPP, ZPP и RP, које су дефинисане користећи пробабилистичке Тјуринове машине. AC и NC, које су дефинисане користећи логички склоп и BQP и QMA, које су дефинисане помоћу квнтне Тјурингове машине. #P је вазжна класа сложености броја проблема (нису проблеми одлучивања). Класе као IP и AM су дефинисане коришћењем интерактивних доказа система. ALL је класа за све проблеме одлучивања.

Редукција

Многе класе сложености су дефинисане коришћењем појма редукције. Редукција је трансформација једног проблема у други проблем. Она обухвата неформалан појам проблема који је једнако тежак као и други проблеми. На пример, ако се проблем X може решити коришћењем алгоритма Y, X није много тежи од Y, и ми кажемо да је X редукција Y. Постоји много различитих врста редукције, на основу метода редукције, као што је Cook редукција, Karp редукција и Levin редукција, и границе сложености редукције тако да је смаљено полиномијално време или смањен логаритамски простор.

Најчешћа употреба редукције полиномијално време редукције. То значи да је за поцес редукције потребно полиноијално време. На пример, проблем квадрирања целог броја може да се редукује на проблем множења два цела броја. То значи да алгоритам за множење два цела броја може да се користи за квадратни цео број. Заиста, то може да се уради тако што је исти улаз за оба улаза множења алгоритама. Тако видимо да квадрирање није теже од множења, јер квадрирање може да се сведе на множење.

Ова мотивација концепта проблема је тежа за класе сложености. Проблем X је тежи од класе проблема C ако сваки проблем у C може бити редукција од X. Проблем у C је тежи него у X, јер нам алгоритам за X омогућава да решимо сваки проблем у C. Наравно, појам тешки проблеми зависи од редукције која се користи. За класе сложеноти веће од P, полиномијално време редуцкције се најчешће користи. Конкретно, низ проблема који су тешки за NP је низ NP - тешких проблема.

Ако је проблем X и C и тешко C, онда је X потпуно за C. То значи да је X најтежи проблем у C. (Од много проблема који су подједнако тешки, могло би се рећи да је X један од најтежих проблема у C). Тако класа NP-комплетних проблема садржи најтеже проблеме у NP, у смислу да они највероватније не би били у P. Пошто проблем P = NP није решен, постоји могућност да се редукује други проблем, Π₁, познато као NP-комплетних проблема, Π₂, указује да нема познатог решења полиномијалног времена за Π₁. То је зато што решење полиномијалног времена за Π₁ добија решење полиномијалног времена за Π₂. Слично томе, јер сви NP проблеми се могу свести на редукцију низа, за проналажење NP-комплетних проблема који се могу решити у полиномијалном времену важи P = NP.

Затвореност особина класе

Класе сложености имају различите особине затворености. На пример, одлука класе може бити затворена под негацијом, дисјункцијом, конјукцијом или чак у свим логичким операцијама. Осим тога, оне такоже могу бити затворене под разним квантификацијама шеме. P, на пример, је ѕатворен према свим логичким операцијама, а квантификација преко полиномијалне величине домена. Међутим, то највероватније није затвореност за квантификацију реко експоненцијалне велчине домена.

Свака класа X која није затворена под негацијом има додатак класе co-Y, која се састоји од комплемената који су садржани у X. Слично се може дефинисати и логичко затворење класе, итд. Ово је, међутим ређе урађено.

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

Односи између класа сложености

Следећа таблица показује неке класе проблема (или језика, или грматика) који се разматрају у теорији сложености. Ако је класа X прави подскуп од Y, тада је X доле приказан испод Y, при чему их повезује тамна линија. Ако је X подскуп, али се не зна јесу ли скупови једнаки, тада је линија светлија и тачкаста. Технички, подела у одлучиве и неодлучиве проблеме више спада у теорију израчунљивости, али и помаже у пружању перспективе над класама сложености.

		Проблем одлучивања
Тип 0 (Рекурзивно пребројив)				Неодлучив
Одлучив
EXPSPACE
NEXPTIME
EXPTIME
PSPACE
Тип 1 (Контексно сензитиван)
		co-NP	BQP		NP
			BPP
		P
	NC
Тип 2 (Контексно независан)
Тип 3 (Регуларан)

Хијерархија теорема

За класе сложености дефинисане на овај начин, пожељно је доказати да опуштање услова за (рецимо) рачунање времена заиста дефинише већи скуп проблема. Конкретно, иако се DTIME(n) налази у DTIME(n²), било би пожељно знти да ли је укључивање строго. За захев за време и простор, одговор на таква питања даје Теорема о времену простору респективно. Они се зову хијерархијска теорема јер изазивају одговарајућу хијерархију о класама дефинисане ограничавајућим одговарајућим ресурсима. Тако постоје парови класа сложености који су исправно укључени једна у другу. Пошто је закључио такве праве постављене додатке, можемо да наставимо о квантитивним изјавама о томе како је потребно много више додатног времена или простора у циљу повећања броја проблема који се могу решити.

Тачније Теорема време хијерархије наводи да:

$\operatorname {DTIME} {\big (}f(n){\big )}\subsetneq \operatorname {DTIME} {\big (}f(n)\cdot \log ^{2}(f(n)){\big )}$.

Теорема простор хијерархије наводи да:

$\operatorname {DSPACE} {\big (}f(n){\big )}\subsetneq \operatorname {DSPACE} {\big (}f(n)\cdot \log(f(n)){\big )}$.

Теорема време и просто хијерархије предсрављају основу за већину резултта класа сложености раздвајања. На пример, Теорема време хијерахије нам говори да ли је P строго садржан у EXPTIME, а Теорема простор хијерархије нам говори да је L строго садржан у PSPACE.

Литература

• The Complexity Zoo Архивирано на сајту Wayback Machine (27. август 2019): A huge list of complexity classes, a reference for experts.
• Neil Immerman. „Computational Complexity Theory”. Архивирано из оригинала 2016-04-16. г.  Includes a diagram showing the hierarchy of complexity classes and how they fit together.
• Michael Garey, and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. The standard reference on NP-Complete problems - an important category of problems whose solutions appear to require an impractically long time to compute.