P (komplikeco)

En komputa komplikteorio, **P** estas komplikeca klaso de decidaj problemoj, kiuj povas esti solvitaj per determinisma maŝino de Turing en polinoma tempo.

**P** estas ofte konsiderata kiel klaso de komputaj problemoj kiu estas sufiĉe rapide solveblaj, kvankam estas eble pli grandaj klasoj ankaŭ kiuj estas konsiderataj kiel sufiĉe rapide solveblaj - **RP** kaj **BPP**. Ankaŭ, ekzistas problemoj en **P** kiuj estas tro malfacilaj en praktiko, ekzemple, se iu postulas almenaŭ *n100000* operaciojn.

## Rilataj komplikeco-klasoj 
**P** estas minimume same granda kiel **L**, la klaso de problemoj decideblaj en logaritma kvanto de memora spaco. Kun uzo de spaco *O(log n)* ne povas esti uzata tempo pli granda ol *2O(log n) = nO(1)*, ĉar ĉi tiu estas la entuta kvanto de eblaj konfiguroj, konservataj en la memoro. Poste ĉi tiom da paŝoj la algoritmo devas nepre aŭ finiĝi aŭ ripetiĝi de iu jam estinta stato kaj tiel neniam finiĝi. Tial, **L** estas subaro de **P**. Ne estas sciata ĉu **L** = **P**.

Estas sciate ke **P** = **AL**, kie **AL** estas klaso de problemoj solveblaj en logaritma memoro per alterna maŝino de Turing. Ankaŭ estas sciate ke **P** estas ne pli granda ol **PSPACO**, la klaso de problemoj decideblaj en polinoma spaco. Ne estas sciate ĉu **P** = **PSPACO**. **L** estas severe enhavata en **PSPACO**, \mbox{L} \subset \mbox{PSPACO}.

**NP** estas klaso de problemoj decideblaj en polinoma tempo per nedeterminisma maŝino de Turing. **P** estas subaro de **NP**. Kvankam la ilia kompara P = NP problemo estas nesolvita, oni plejparte kredas ke veras la *nea* respondo al la demando ĉu **P** = **NP**, alivorte **P** estas severa subaro de **NP**, aŭ alivorte estas problemoj kiuj estas decideblaj en polinoma tempo per nedeterminisma maŝino kaj ne estas decideblaj en polinoma tempo per determinisma maŝino.

**EKSPTEMPO** estas klaso de problemoj solveblaj en eksponenta tempo. **P** estas severe enhavata en **EKSPTEMPO**, \mbox{P} \subset \mbox{EKSPTEMPO}. Do, ĉiuj **EKSPTEMPO**-pezaj problemoj kuŝas ekster **P**.

Tiel:

:\mbox{L} \subseteq \mbox{AL} = \mbox{P} \subseteq \mbox{NP} \subseteq \mbox{PSPACO} \subseteq \mbox{EKSPTEMPO}

kune kun tio ke por ĉi tiuj klasoj du (kaj nur du) severaj neegalaĵoj estas sciataj:

* \mbox{P} \subset \mbox{EKSPTEMPO}, do almenaŭ unu el la enhavecoj dekstren de **P** en la formulo pli supre estas severa. Fakte, oni plejparte kredas ke ĉiuj tri estas severaj.
* \mbox{L} \subset \mbox{PSPACO}

La plej malfacilaj problemoj en P estas P-plenaj problemoj.

Alia ĝeneraligo de **P** estas **P/poli**, aŭ **neuniforma polinoma tempo**. Se problemo estas en **P/poli**, do ĝi povas esti solvita per determinisma maŝino en polinoma tempo se konsila linio estas donita, kiu dependas nur de longo de la enigo. Malsimile al **NP**, tamen, la **P/poli** algoritmo ne bezonas konsilon dependan de la enigo, **P/poli** algoritmo ne estas nur kontrolilo. **P/poli** estas granda klaso enhavanta preskaŭ ĉiujn praktikajn algoritmojn, inkluzivante ĉiujn de **BPP**. Se **P/poli** enhavas **NP**, tiam la polinoma hierarkio kolapsas al la dua nivelo. Aliflanke, **P/poli** enhavas ankaŭ iujn nepraktikajn algoritmojn, inkluzivante iujn nedecideblajn problemojn.

En 1999, Jin-Yi Cai kaj D. Sivakumar, montris ke se tie ekzistas polinome limigita lingvo kiu estas **P**-plena, tiam **L** = **P**.

## Rimarkindaj problemoj en P 
**P** enhavas multaj ofte estantajn problemojn. Inter ili estas la decida versio de lineara programado, kalkulo de la plej granda komuna divizoro, primeco-testo. La rilatanta klaso de funkciaj problemoj estas **FP**.

Kelkaj naturaj problemoj estas plenaj en **P**, ekzemple *st*-konekteco (aŭ atingebleco) sur alterna grafeoj .

## Propraĵoj 
Polinomo-tempaj algoritmoj estas fermitaj sub komponaĵo. Ĉi tio signifas ke se estas funkcio kiu estas polinomo-tempa kondiĉe ke la uzata subfunkcio estas konstanto-tempa, kaj se la subfunkcio mem estas tamen polinomo-tempa, tiam la tuta algoritmo estas polinomo-tempa. Unu konsekvenco de tio estas ke **P** estas malalta mem. Ĉi tio estas ankaŭ unu el la ĉefaj kaŭzoj de tio ke **P** estas konsiderita kiel komputil-sendependa klaso, ĉar ĉiu realisma maŝino povas ruligi programon de ĉiu alia maŝino en polinoma tempo por ĉiu unu operacio.

## Puraj pruvoj de ekzisto de polinomo-tempaj algoritmoj 
Iuj problemoj estas sciataj kiel solveblaj en polinoma tempo, sed neniu konkreta algoritmo estas konata por ili kun polinoma tempo. Ekzemple, la teoremo de Robertson-Seymour garantias ke estas finita listo de malpermesataj minoroj kiuj karakterizas (ekzemple) la aron de grafeoj kiuj povas esti enigitaj sur toron; ankaŭ, Robertson kaj Seymour montris ke estas algoritmo kun komplikeco *O(n3)* por kontroli ĉu donita grafeo enhavas la alian donitan grafeon kiel minoro. Ĉi tio signifas ke ekzistas polinomo-tempa algoritmo por kontroli ĉu donita grafeo povas esti enigita sur toron. Tamen la pruvo estas nekonstruanta pruvo kaj neniu konkreta algoritmo estas sciata por solvado de ĉi tiu problemo.

## Eksteraj ligiloj 
* Komplikeca zoo: P , P/poli 

Kategorio:Komputa komplikeco