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ŭ n¹⁰⁰⁰⁰⁰ operaciojn.

Rilatantaj komplikecaj 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 2^{O(log n)} = n^O(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.^[1]

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 ^[2].

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(n³) 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

↑ Jin-Yi Cai, D. Sivakumar. Sparse hard sets for P: resolution of a conjecture of Hartmanis - Polinome limigite pezaj aroj por P: rezolucio de konjekto de Hartmanis. Journal of Computer and System Sciences - Ĵurnalo de komputilaj kaj sistemaj sciencoj, volumo 58, numero 2, pp.280-296. 1999. ISSN:0022-0000. Je Citeseer Arkivigite je 2007-11-09 per la retarkivo Wayback Machine
↑ Immerman, Neil. (1999) Descriptive Complexity - Priskriba komplikeco. Nov-Jorkio: Springer-Verlag. ISBN 0-387-98600-6.

Komplikeca zoo: P Arkivigite je 2006-11-28 per la retarkivo Wayback Machine, P/poli Arkivigite je 2006-11-28 per la retarkivo Wayback Machine

[1] Jin-Yi Cai, D. Sivakumar. Sparse hard sets for P: resolution of a conjecture of Hartmanis - Polinome limigite pezaj aroj por P: rezolucio de konjekto de Hartmanis. Journal of Computer and System Sciences - Ĵurnalo de komputilaj kaj sistemaj sciencoj, volumo 58, numero 2, pp.280-296. 1999. ISSN:0022-0000. Je Citeseer Arkivigite je 2007-11-09 per la retarkivo Wayback Machine

[2] Immerman, Neil. (1999) Descriptive Complexity - Priskriba komplikeco. Nov-Jorkio: Springer-Verlag. ISBN 0-387-98600-6.

[1]

[2]