П (сложеност)

У рачунарској теорији сложености, P позната као PTIME или DTIME (n^O(1)) је једна од фундаменталних класа сложености. Она садржи све проблеме одлучивања који могу да се реше помоћу детерминистичке Тјурингове машине коришћењем полиномне количине времена рачунарске обраде т.ј. полиномијалног времена. Кобхамова теза утврђује да је P класа рачунарских проблема који могу „ефикасно да се реше“ т.ј. „трактабилни су“. У пракси неки проблеми који нису у класи P имају практично решење, а неки који су у P немају.

Дефиниција

Језик L је у P ако и само ако постоји детерминистичка Тјурингова машина M таква да:

M ради у полиномијалном времену за све улазе
за све x из L, M даје 1
за све x који нису из L, M даје 0

На P може да се гледа као на унифромну фамилију логичких кола. Језик L је у P ако и само ако постоји униформна фамилија логичких кола у полиномијалном времену $\{C_{n}:n\in \mathbb {N} \}$ , таква да:

за свако $n\in \mathbb {N}$ , $C_{n}$ узима n битова на улазу и на излазу даје 1 бит
за свако x из L, $C_{|x|}(x)=1$
за свако x које није у L, $C_{|x|}(x)=0$

Дефиниција кола може да буде слабија тако што ће се користити само logspace униформна фамилија кола, без промене класе сложености.

Значајни проблеми у P

За P се зна да садржи многе природне проблеме укључујући верзије одлучивања линеарног програмирања, израчунавања највећег заједничког делиоца и налажење максималног уклапања. 2002. године је показано да је проблем одређивања да ли је неки број прост број, такође у P.^[1] Сродна класа функцијских проблема је FP. Неколико функцијских проблема су комлетни за P, укључујући st повезаност (доступност) на алтернирајућим графовима. У чланку о P комплетним проблемима даље се наводе релевантни проблеми из P.

Релације према другим класама

Генерализација P је NP која је класа проблема одлучивања који извршава недетерминистичка Тјурингова машина у полиномијалном времену. Исто тако, то је класа проблема одлучивања где свака појава „да“ носи потврду полиномијалне величине, а потврде могу да се провере помоћу детерминистичке Тјурингове машине у полиномијалном времену. Класа проблема за које је ово истина за појаве „не“, назива се co-NP. P је, једноставно, подскуп NP и co-NP. Већина стручњака верује да се ради о правом подскупу,^[2] иако то још увек није доказано ( ${P}\subseteq {\mbox{NP}}$ P ≠ NP хипотеза). Још један нерешени проблем је да ли је NP = co-NP (негативни одговор имплицира ${P}\subseteq {\mbox{NP}}$ ). Зна се да је P најмање величине L – класе проблема одлучивих у оквиру логаритамске количине меморијског простора. Одлучивање које користи $O(\log n)$ простора, не може да траје дуже од $2^{O(\log n)}=n^{O(1)}$ зато што је то укупан број могућих конфигурација и тако следи је L подскуп P. Други важан проблем је да ли је L = P. Знамо да је P = AL, скупу проблема решивих у логаритамској меморији помоћу алтернирајуће Тјурингове машине. За P се зна да није већи од PSPACE – класе проблема одлучивих у полиномијалном простору. Опет, да ли је P = PSPACE је отворен проблем. Да закључимо:

{\mbox{L}}\subseteq {\mbox{AL}}={\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PSPACE}}\subseteq {\mbox{EXPTIME}}.

Овде је EXPTIME класа проблема решивих у експоненцијалном времену. Од свих класа које су приказане, зна се за само две стриктне припадности:

P се стриктно садржи у EXPTIME. Сходно томе, сви EXPTIME – тешки проблеми, леже ван P и барем једна од припадности десно од P је строга (у ствари, широко распрострањено веровање је да су све три строге).
L је стриктно садржана у PSPACE.

Најтежи проблеми у P су P – комплетни проблеми.

Још једна генерализација P је P/poly или неуниформно полиномијално време. Ако је проблем у P/poly, онда може да буде решен у детерминистичком полиномијалном времену уз услов да је дат помоћни низ (advice string) који зависи једино од дужине улаза. За разлику од NP, машина са полиномијалним временом нема потребе за детекцијом погрешних помоћних низова – она није верификатор. P/poly је велика класа која садржи скоро све практичне проблеме, уклјучујући све из BPP. Ако садржи NP, тада се полиномијална хијерархија скраћује на други ниво. Са друге стране, ова класа садржи и неке проблеме на које не наилазиму у пракси укључујући неодлучиве проблеме као што је унарна визија било ког неодлучивог проблема. Јин-Ји Каи и Д. Сивакумар, су 1999. године, разрађујући тезе из рада Мицунори Огихаре, показали да ако постоји оскудан језик (sparse language) који је P-комплетан, онда важи L = P.^[3]

Особине

Алгоритми са полиномијалним временом су затворени приликом састављања. Ово значи да ако неко напише функцију која је временски полиномијална, под претпоставком да се позиви функција одвијају у константном времену, а позване функције се, такође, извршавају у полиномијалном времену, тада цео алгоритам ради у полиномијалном времену. Једна последица овога је да је P ниска по себи. То је, такође, један од основних разлога да се P посматра као класа независна од машине. Свака одлика машине, као на пример насумичан (случајан) приступ (random access) која се може симулирати у полиномијалном времену, може се представити главним алгоритмом у полиномијалном времену и тако свести на алгоритам који се изводи на једноставнијој машину, исто тако у полиномијалном времену.

Језици у P су такође затворени код негација, пресека, унија, конкатенација, Клинијевог затварања, инверзије, хомоморфизма и комплементације.^[4]

Докази о постојању алгоритама полиномијалног времена

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

Алтернативне карактеризације

У дескриптивној сложености (descriptive complexity), класа P може да се опише проблемима израженим у FO(LFP), логиком првог реда са оператором најмање фиксне тачке (least fixed point) додатим на уређену структуру. У књизи Имермана из 1999. године о дескриптивној сложености, и себи.^[5] 2001. године је објављено да PTIME одговара позитивним граматикама конкатенације слогова (range concatenation grammars).^[6]

Историја

Козен^[7] тврди да су Кобем и Едмондс „генерално заслужни за изум појма полиномијалног времена“. Кобем је измислио класу, као моћан начин за карактеризацију ефикасних алгоритама, што је довела до Кобемове тезе. Ипак, Х. C. Поклингтон је још давне 1910. године објавио рад у коме је анализирао два алгоритма за решавање квадратне конгруенције. Он је увидео да је један утрошио време „пропорционално степену логаритма модула“, а други време „пропорционално самом модулу или његовом квадратном корену“. Тако је Поклингтон направио јасну разлику између алгоритма који се извршава у полиномијалном времену у односу на други, који се не извршава у полиномијалном времену.

Референце

^ Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2. стр. 781–793.
^ Johnsonbaugh, Richard; Schaefer, Marcus, Algorithms, 2004 Pearson Education. ISBN 978-0-02-360692-2. стр. 458.
^ Jin-Yi Cai and D. Sivakumar. Sparse hard sets for P: resolution of a conjecture of Hartmanis. Journal of Computer and System Sciences, volume 58, issue 2. стр. 280-296. 1999. ISSN 0022-0000. At Citeseer Архивирано на сајту Wayback Machine (9. новембар 2007)
^ Hopcroft 2001, стр. 425–426
^ Immerman, Neil (1982). „Relational Queries Computable in Polynomial Time”. STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing. стр. 147—152. doi:10.1145/800070.802187. Revised version in Information and Control, 68 (1986), 86–104.
^ Kallmeyer 2010, стр. 5, 37.
^ Kozen 2006, стр. 4.

Литература

Kozen, Dexter C. (2006). Theory of Computation. Springer. стр. 4. ISBN 978-1-84628-297-3.
Kallmeyer, Laura (2010). Parsing Beyond Context-Free Grammars. Springer Science & Business Media. ISBN 978-3-642-14846-0.
Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Introduction to automata theory, languages, and computation (2. изд.). Boston: Addison-Wesley. стр. 425–426. ISBN 978-0-201-44124-6.
Кобхам Алан (1965). "The intrinsic computational difficulty of functions".
Томас Х. Кормен, Чарлс E. Лајсерсон, Роналд Лин Ривест и Клифорд Стајн, Introduction to Algorithms (Увод у алгоритме), друго издање. MIT Press и McGraw–Hill, 2001. Section 34.1: Polynomial time. стр. 971-979.
Christos H. Papadimitriou (1994). Computational complexity.
Sipser, Michael (2006). Introduction to the Theory of Computation (2nd изд.).

.

[1] Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2. стр. 781–793.

[2] Johnsonbaugh, Richard; Schaefer, Marcus, Algorithms, 2004 Pearson Education. ISBN 978-0-02-360692-2. стр. 458.

[3] Jin-Yi Cai and D. Sivakumar. Sparse hard sets for P: resolution of a conjecture of Hartmanis. Journal of Computer and System Sciences, volume 58, issue 2. стр. 280-296. 1999. ISSN 0022-0000. At Citeseer Архивирано на сајту Wayback Machine (9. новембар 2007)

[4] Hopcroft 2001, стр. 425–426

[5] Immerman, Neil (1982). „Relational Queries Computable in Polynomial Time”. STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing. стр. 147—152. doi:10.1145/800070.802187. Revised version in Information and Control, 68 (1986), 86–104.

[FOOTNOTEKallmeyer20105,_37-6] Kallmeyer 2010, стр. 5, 37.

[FOOTNOTEKozen20064-7] Kozen 2006, стр. 4.

[1]

[2]

[3]

[4]

[5]

[6]

[7]