| dbo:abstract
|
- En teoria de la complexitat, la classe de complexitat NL és la classe dels problemes de decisió que es poden resoldre per una màquina de Turing no determinista usant una quantitat logarítmica d'espai. NL és una generalització de la classe L. Ja que tota màquina de Turing determinista és també una màquina de Turing no determinsita, L està dins de NL. NL es pot definir en termes de recursos com NL = NSPACE (log n). (ca)
- في نظرية التعقيد الحسابي ان إل (غير قطعية لوغارتمية المساحة) (nondetereministic logarithmic-space) NL هي قسم من اللغات الصورية تضم مسائل التقرير التي يمكن حلها باستخدام كمية لوغارتمية من الذاكرة بواسطة آلة تورينغ غير قطعية. NL هي تعميم لL وهي قسم المسائل اللوغارتمية المكان القطعية، وحيث إن كل آلة تورينغ قطعية هي أيضا آلة تورينغ غير قطعية، فإن L تنتمي إلى NL. (ar)
- En , NL estas la enhavanta kiu povas esti solvita per nedeterminisma maŝino de Turing uzante logaritman kvanton de . 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: (x1 aŭ ~x3) kaj (~x2 aŭ x3) kaj (~x1 aŭ ~x2) 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 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 operatoro. (eo)
- In der Komplexitätstheorie bezeichnet NL (für nichtdeterministisch logarithmischer Platz) die Klasse der Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine auf logarithmischem Platz gelöst werden können. NL ist eine Erweiterung der Klasse L, die analog für deterministische Turingmaschinen definiert ist. (de)
- En teoría de la complejidad computacional, la clase de complejidad NL (espacio logarítmico no determinista) es el conjunto de los problemas de decisión que pueden ser resueltos en espacio log(n) (sin contar el tamaño de la entrada), donde n es el tamaño de la entrada, por una máquina de Turing no determinista tal que la solución, si existe, es única. La clase L está contenida en NL y está contenida estrictamente en PSPACE. Como NL también está contenida estrictamente en PSPACE, se concluye que en la relación NL es diferente de PSPACE, pero aparte de eso es posible por cada inclusión que las clases sean iguales o no.
* Datos: Q12857599 (es)
- In computational complexity theory, NL (Nondeterministic Logarithmic-space) is the complexity class containing decision problems that can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space. NL is a generalization of L, the class for logspace problems on a deterministic Turing machine. Since any deterministic Turing machine is also a nondeterministic Turing machine, we have that L is contained in NL. NL can be formally defined in terms of the computational resource nondeterministic space (or NSPACE) as NL = NSPACE(log n). Important results in complexity theory allow us to relate this complexity class with other classes, telling us about the relative power of the resources involved. Results in the field of algorithms, on the other hand, tell us which problems can be solved with this resource. Like much of complexity theory, many important questions about NL are still open (see Unsolved problems in computer science). Occasionally NL is referred to as RL due to its below; however, this name is more frequently used to refer to randomized logarithmic space, which is not known to equal NL. (en)
- En informatique théorique, plus précisément en théorie de la complexité, NL est une classe de complexité. Cette classe est aussi appelée NLogSpace[réf. nécessaire]. C'est l'ensemble des problèmes de décision qui peuvent être décidés par des machines de Turing non déterministes dont l'espace de travail est borné par une fonction logarithmique. (fr)
- 계산 복잡도 이론에서 NL(Nondeterministic Logarithmic-space)은 비결정론적 튜링 기계가 로그 기억 공간을 써서 풀 수 있는 판정 문제의 복잡도 종류이다. NL은 결정론적 튜링 기계에서 로그 공간을 들여 풀 수 있는 문제의 집합인 L을 일반화한 것이다. 모든 결정론적 튜링 기계는 비결정론적 튜링 기계이기도 하기 때문에, L은 NL에 들어간다. NL의 공식적인 정의는 (곧 NSPACE)이라는 계산 자원 개념을 사용해서 한다. 이에 따르면 NL = NSPACE(log n)이다. NL은 아래 나오는 때문에 RL이라고도 한다. 그러나 RL은 를 나타내는 데 주로 쓰인다. (ko)
- NL（えぬえる、英: Nondeterministic Logarithmic-space）は、計算複雑性理論における決定問題の複雑性クラスの一つである。非決定性チューリングマシンで対数規模の記憶領域を使って解ける問題がこのクラスに属する。 NL は Lを一般化したものである。L は決定性チューリングマシンでの対数領域問題のクラスである。決定性チューリングマシンは非決定性チューリングマシンに含まれるため、L も NL に含まれる。 NLは非決定性領域(NSPACE)の計算資源記法で形式的に定義でき、NL = NSPACE(log n) となる。 計算複雑性理論の研究により、このクラスと他の複雑性クラスの関係が明らかとなり、必要な計算資源も明らかとなってきた。一方、アルゴリズムの研究によって、対数領域で解ける問題も明らかとなってきつつある。しかし、計算複雑性理論の他の分野と同様、NLについての重要な部分は未解決である。 NLの（後述）を指して RL と呼ぶこともある。しかし、RLという名称はRLPという複雑性クラスの別名として使われることが多い（RLPとは、確率的チューリングマシンで対数領域と多項式時間で解ける問題のクラス）。 (ja)
- La classe NL (abbreviazione di nondeterministic logarithmic space, ovvero "spazio logaritmico non deterministico", nota anche come NLOGSPACE) è una classe di complessità di problemi accettati da una macchina di Turing non deterministica in spazio logaritmico ossia con . Visto che un problema accettato da una macchina deterministica lo è anche da una non deterministica, avremo che . (it)
- Na teoria da complexidade, NL (espaço-logarítmico não-determinístico) é a classe de complexidade contendo problemas de decisão que podem ser resolvidos por uma máquina de Turing não-determinística, usando uma quantidade de espaço de memória logarítmica. NL é uma generalização de L, a classe dos problemas de espaço logarítmico em uma máquina de Turing determinística. Desde que qualquer máquina de Turing seja também uma máquina de Turing não-determinística, nós temos que L está contida em NL. NL pode ser formalmente definida em termos de recursos computacionais de espaço não-determinístico (ou NSPACE) como NL = NSPACE(log n). Importantes resultados em teoria da complexidade nos permitem relacionar esta classe de complexidade com outras classes, dizendo-nos algo sobre o poder relativo dos recursos envolvidos. Resultados na área de algoritmos, por outro lado, nos informam quais problemas podem ser resolvidos com este recurso. Infelizmente, como grande parte da teoria da complexidade, muitas questões importantes sobre NL ainda estão abertas. Ocasionalmente, NL é referida como RL devido a sua definição probabilística abaixo. No entanto, esse nome é mais frequentemente usado para referir espaços logarítmicos aleatórios, o qual não é conhecido como sendo NL. (pt)
- Клас мов L — множина мов, розв'язних на детермінованій машині Тюрінга з використанням додаткової пам'яті для входу довжиною n. Клас мов NL — множина мов, розв'язних на недетермінованій машині Тюрінга з використанням додаткової пам'яті для входу довжиною n. Приклади:
*
* Нехай мова — орієнтований граф, у якому є шлях від до , тоді (uk)
- Класс языков L — множество языков, разрешимых на детерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной n. Класс языков NL — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной n. Примеры:
*
* Пусть язык — ориентированный граф в котором есть путь от s до t, тогда (ru)
|
| rdfs:comment
|
- En teoria de la complexitat, la classe de complexitat NL és la classe dels problemes de decisió que es poden resoldre per una màquina de Turing no determinista usant una quantitat logarítmica d'espai. NL és una generalització de la classe L. Ja que tota màquina de Turing determinista és també una màquina de Turing no determinsita, L està dins de NL. NL es pot definir en termes de recursos com NL = NSPACE (log n). (ca)
- في نظرية التعقيد الحسابي ان إل (غير قطعية لوغارتمية المساحة) (nondetereministic logarithmic-space) NL هي قسم من اللغات الصورية تضم مسائل التقرير التي يمكن حلها باستخدام كمية لوغارتمية من الذاكرة بواسطة آلة تورينغ غير قطعية. NL هي تعميم لL وهي قسم المسائل اللوغارتمية المكان القطعية، وحيث إن كل آلة تورينغ قطعية هي أيضا آلة تورينغ غير قطعية، فإن L تنتمي إلى NL. (ar)
- In der Komplexitätstheorie bezeichnet NL (für nichtdeterministisch logarithmischer Platz) die Klasse der Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine auf logarithmischem Platz gelöst werden können. NL ist eine Erweiterung der Klasse L, die analog für deterministische Turingmaschinen definiert ist. (de)
- En informatique théorique, plus précisément en théorie de la complexité, NL est une classe de complexité. Cette classe est aussi appelée NLogSpace[réf. nécessaire]. C'est l'ensemble des problèmes de décision qui peuvent être décidés par des machines de Turing non déterministes dont l'espace de travail est borné par une fonction logarithmique. (fr)
- 계산 복잡도 이론에서 NL(Nondeterministic Logarithmic-space)은 비결정론적 튜링 기계가 로그 기억 공간을 써서 풀 수 있는 판정 문제의 복잡도 종류이다. NL은 결정론적 튜링 기계에서 로그 공간을 들여 풀 수 있는 문제의 집합인 L을 일반화한 것이다. 모든 결정론적 튜링 기계는 비결정론적 튜링 기계이기도 하기 때문에, L은 NL에 들어간다. NL의 공식적인 정의는 (곧 NSPACE)이라는 계산 자원 개념을 사용해서 한다. 이에 따르면 NL = NSPACE(log n)이다. NL은 아래 나오는 때문에 RL이라고도 한다. 그러나 RL은 를 나타내는 데 주로 쓰인다. (ko)
- NL（えぬえる、英: Nondeterministic Logarithmic-space）は、計算複雑性理論における決定問題の複雑性クラスの一つである。非決定性チューリングマシンで対数規模の記憶領域を使って解ける問題がこのクラスに属する。 NL は Lを一般化したものである。L は決定性チューリングマシンでの対数領域問題のクラスである。決定性チューリングマシンは非決定性チューリングマシンに含まれるため、L も NL に含まれる。 NLは非決定性領域(NSPACE)の計算資源記法で形式的に定義でき、NL = NSPACE(log n) となる。 計算複雑性理論の研究により、このクラスと他の複雑性クラスの関係が明らかとなり、必要な計算資源も明らかとなってきた。一方、アルゴリズムの研究によって、対数領域で解ける問題も明らかとなってきつつある。しかし、計算複雑性理論の他の分野と同様、NLについての重要な部分は未解決である。 NLの（後述）を指して RL と呼ぶこともある。しかし、RLという名称はRLPという複雑性クラスの別名として使われることが多い（RLPとは、確率的チューリングマシンで対数領域と多項式時間で解ける問題のクラス）。 (ja)
- La classe NL (abbreviazione di nondeterministic logarithmic space, ovvero "spazio logaritmico non deterministico", nota anche come NLOGSPACE) è una classe di complessità di problemi accettati da una macchina di Turing non deterministica in spazio logaritmico ossia con . Visto che un problema accettato da una macchina deterministica lo è anche da una non deterministica, avremo che . (it)
- Клас мов L — множина мов, розв'язних на детермінованій машині Тюрінга з використанням додаткової пам'яті для входу довжиною n. Клас мов NL — множина мов, розв'язних на недетермінованій машині Тюрінга з використанням додаткової пам'яті для входу довжиною n. Приклади:
*
* Нехай мова — орієнтований граф, у якому є шлях від до , тоді (uk)
- Класс языков L — множество языков, разрешимых на детерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной n. Класс языков NL — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной n. Примеры:
*
* Пусть язык — ориентированный граф в котором есть путь от s до t, тогда (ru)
- En , NL estas la enhavanta kiu povas esti solvita per nedeterminisma maŝino de Turing uzante logaritman kvanton de . 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. (x1 aŭ ~x3) kaj (~x2 aŭ x3) kaj (~x1 aŭ ~x2) Estas simpla logika karakterizado de NL: ĝi enhavas precize lingvojn esprimeblajn en unua ordo logiko kun aldonita operatoro. (eo)
- En teoría de la complejidad computacional, la clase de complejidad NL (espacio logarítmico no determinista) es el conjunto de los problemas de decisión que pueden ser resueltos en espacio log(n) (sin contar el tamaño de la entrada), donde n es el tamaño de la entrada, por una máquina de Turing no determinista tal que la solución, si existe, es única. La clase L está contenida en NL y está contenida estrictamente en PSPACE. Como NL también está contenida estrictamente en PSPACE, se concluye que en la relación
* Datos: Q12857599 (es)
- In computational complexity theory, NL (Nondeterministic Logarithmic-space) is the complexity class containing decision problems that can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space. NL is a generalization of L, the class for logspace problems on a deterministic Turing machine. Since any deterministic Turing machine is also a nondeterministic Turing machine, we have that L is contained in NL. NL can be formally defined in terms of the computational resource nondeterministic space (or NSPACE) as NL = NSPACE(log n). (en)
- Na teoria da complexidade, NL (espaço-logarítmico não-determinístico) é a classe de complexidade contendo problemas de decisão que podem ser resolvidos por uma máquina de Turing não-determinística, usando uma quantidade de espaço de memória logarítmica. NL é uma generalização de L, a classe dos problemas de espaço logarítmico em uma máquina de Turing determinística. Desde que qualquer máquina de Turing seja também uma máquina de Turing não-determinística, nós temos que L está contida em NL. (pt)
|
