NL (komplikeco)

En komputa komplikteorio, NL estas la komplikeca klaso enhavanta decidajn problemojn kiu povas esti solvita per nedeterminisma maŝino de Turing uzante logaritman kvanton de memora spaco.

NL estas ĝeneraligo de L, la klaso de decidaj problemoj kiuj povas esti solvita per determinisma maŝino de Turing uzante logaritman kvanton de memora spaco. Pro tio ke ĉiu determinisma Maŝino de Turing estas ankaŭ nedeterminisma maŝino de Turing, L estas enhavita en NL.

Problemo de kontrolo ĉu vojo ekzistas inter du verticoj en orientita grafeo estas ekzemplo de grava problemo kiu estas sciata al esti plenuma por NL. En intuicia senco, ĝi estas unu de la plej pezaj aŭ plej esprimaj problemoj en NL. Alia grava NL-plena problemo estas 2-bulea plenumebloproblemo, kiu demandas, ĉu, por donita formulo kie ĉiu propozicio estas la disjunkcio de du variabloj, estas tia aro de enigaj variabloj kiu faras la formulon egalan al "VERO"? Ekzemplo de ĉi tia formulo povas esti:

(x₁ aŭ ~x₃) kaj (~x₂ aŭ x₃) kaj (~x₁ aŭ ~x₂)

Estas sciate, ke NL estas enhavata en P, pro tio ke estas polinomo-tempa algoritmo por 2-bulea plenumebloproblemo, sed ne estas sciate, ĉu NL = P aŭ ĉu L = NL. Pro tio ke nedeterminisma spaco estas fermita sub komplemento, estas sciate, ke NL = co-NL, rezulto sendepende esplorita de Neil Immerman kaj Róbert Szelepcsényi en 1987 (teoremo de Immerman-Szelepcsényi) kaj juĝita la premio de Gödel en 1995.

Tamen, estas sciate, ke NL=RL, la klaso de problemoj solveblaj per probableca maŝino de Turing en logaritma spaco kaj nebarita tempo kiu malĝusta malakcepto kun probablo < 1/3. Ĝi estas ankaŭ egala al ZPL, la klaso de problemoj solveblaj per hazardigitaj algoritmoj en logaritma spaco kaj nebarita tempo sen eraro. Ĝi estas ne, tamen, sciata aŭ kredata esti egala al RLP aŭ ZPLP, la polinomo-tempaj limigoj de RL kaj ZPL kiujn iuj aŭtoroj nomas kiel RL kaj ZPL.

Estas simpla logika karakterizado de NL: ĝi enhavas precize lingvojn esprimeblajn en unua ordo logiko kun aldonita transitiva fermaĵa operatoro.

Referencoj[redakti | redakti fonton]

C. Papadimitriou. Komputa Komplekseco. Addison-Wesley, 1994. ISBN 0-201-53082-1. Ĉapitro 16: Logaritma Spaco.
Sekcio 8.4–8.6 (La Klasoj L kaj NL, NL-pleneco, NL egalas coNL), pp.294–302.