NL (complexitate)

Această intrare despre subiectul matematic al informației și comunicării este doar o schiță . Contribuiți la îmbunătățirea acestuia în conformitate cu convențiile Wikipedia .

Clasa NL este o clasă de complexitate a problemelor acceptate de o mașină Turing nedeterministă în spațiul logaritmic, adică cu ${\displaystyle {\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">S.</span></span>}}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">M.</span></span>}}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">(</span></span>\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">n</span></span>}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">)</span></span><span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">=</span></span>\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">SAU</span></span>}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">(</span></span>\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">Buturuga</span></span>}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;"></span></span>\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">n</span></span>}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">)</span></span>}${\ displaystyle S_ {M} (n) = O (\ log n)} .

Deoarece o problemă acceptată de o mașinărie deterministă este acceptată și de una nedeterministă, o vom avea${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">L</span></span>}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\subseteq </span></span>\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">Nu.</span></span>}\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">L</span></span>}}${\ displaystyle L \ subseteq NL} .

Portal IT

Portalul de matematică