Класа сложености
From Wikipedia, the free encyclopedia
У теорији рачунарске сложености, класа сложености је скуп проблема повезаних ресурсима заснованим на сложености. Типична сложеност класа има дефиницију облика:
- скуп проблема који се могу решити апстрактном машином М коришћењем O(f(n)) ресурса Р, где је n величина улаза.
Сложене класе су забринуте са стопом раста захтева за ресурсе као и повећавање улаза n. То је апстрактно мерење, и не даје време или простор у секунди или бајту, што захтева познавање имплементације специфичности. Функција унутар O(...) израза може бити константа, за алгоритме који су под утицајем величине n, или израза који садржи логаритам, израз укључује n, односно полиномни израз, и многе друге. O се чита као "редослед...". За потребе израчунавања теорије сложености, неке од детаља функције се могу занемарити, на пример много могућих полинома може бити груписано као класа.
Питање ресурса може бити или време, у суштии број примитивних операција на апстрактне машине, или (за складиштење) простор. На пример, класа NP је скуп свих проблема одлучивања који могу бити решени недетерминистичком Тјуринговом машином у полиномијалном времену док је класа PSPACE скуп свих проблема одлуке који могу бити решени детерминистичком Тјуринговом машином у полиномијалном простору.
Најједноставније класе сложености су дефинисане следећим факторима:
- Тип рачунарских проблема: Најчешће коришћени проблеми су проблеми одлучивања. Међутим, класе сложености се могу дефинисати на основу функцијских проблема (пример је FP), рачунарских проблема (нпр.#P), оптимизационих проблема, обећавајућих проблема итд...
- Модел рачунања: Најчешћи модел рачунања је детерминистичка Тјурингова машина, али многе класе сложености су засноване на недетерминистичким Тјуринговим машинама, логички склоп, квантна Тјурингова машина, монотон склоп, итд.
- Ресурс(или ресурси) који се граниче и границе: Ове две особине се обично наводе заједно, као што су "полиномијално време", "логаритамски простор", "константна дубина", итд.
Многе класе сложености се могу окарактерисати као математичка логика која жели да их изрази;
Гранично време израчунавања неке конкретне фукнције f(n) чсто даје сложеност класе која зависи од изабраног модела машине. На пример, језик {xx | x је било који бинарни ниѕ} може да е реши у линеарном ремену на мулти-траци Тјурингове машине, али нужно захтева квадратно време у моделу једне-траке Тјурингове машине. Ако дозволимо полиномијалну варијацију у текућем времену, Cobham-Edmonds теза гласи да је "временска сложеност било која два разумна и општа модела обрачуна су полиномијално везана". Ово представља основу за сложеност класе P, која је низ датих проблема одлуке решена детерминистичком Тјуринговом машином у полиномијалном времену одговарајућег скупа функцијиских проблема је FP.
Блумове аксиоме се могу користити за дефинисање класа сложености без позивања на неки конкретни рачунски модел.