RL (kompleksitet) - RL (complexity)
Randomized Logarithmic-space ( RL ), nogle gange kaldet RLP (Randomized Logarithmic-space Polynomial-time), er kompleksitetsklassen for beregningskompleksitetsteoretiske problemer, der kan løses i logaritmisk rum og polynomisk tid med sandsynlige Turing-maskiner med ensidig fejl . Det navngives i analogi med RP , der ligner, men har ingen logaritmisk pladsbegrænsning.
Definition
De sandsynlige Turing-maskiner i definitionen af RL accepterer aldrig forkert, men har tilladelse til at afvise forkert mindre end 1/3 af tiden; dette kaldes ensidig fejl . Den konstante 1/3 er vilkårlig; ethvert x med 0 < x <1 ville være tilstrækkeligt. Denne fejl kan gøres 2 - p ( x ) gange mindre for enhver polynom p ( x ) uden at bruge mere end polynomisk tid eller logaritmisk plads ved at køre algoritmen gentagne gange.
Forhold til andre kompleksitetsklasser
Nogle gange er navnet RL forbeholdt den klasse af problemer, der kan løses af logaritmiske rum-sandsynlighedsmaskiner i ubegrænset tid. Imidlertid kan denne klasse vise sig at være lig med NL ved hjælp af en sandsynligheds tæller, og kaldes derfor normalt i stedet for NL ; dette viser også, at RL er indeholdt i NL . RL er indeholdt i BPL , der er ens, men tillader tosidet fejl (forkert accepterer). RL indeholder L , de problemer, der kan løses af deterministiske Turing-maskiner i logrummet, da dens definition bare er mere generel.
Noam Nisan viste i 1992 det svage derandomiseringsresultat, at RL er indeholdt i SC , klassen af problemer, der kan løses i polynomial tid og polylogaritmisk rum på en deterministisk Turing-maskine; med andre ord, givet polylogaritmisk rum, kan en deterministisk maskine simulere logaritmiske rum-probabilistiske algoritmer.
Det antages, at RL er lig med L , det vil sige, at polynom-tid logspace-beregning kan fuldstændigt derandomiseres; vigtigste beviser for dette blev præsenteret af Reingold et al. i 2005. Et bevis på dette er den hellige gral for indsatsen inden for ubetinget derandomisering af kompleksitetsklasser. Et stort skridt fremad var Omer Reingold s bevis på, at SL er lig med L .
