NL (complexity) (original) (raw)
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).
| Property | Value |
|---|---|
| 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) |
| dbo:wikiPageExternalLink | https://archive.org/details/introductiontoth00sips/page/294 https://web.archive.org/web/20160303183247/http:/www.wisdom.weizmann.ac.il/~oded/PS/CC/l7.ps |
| dbo:wikiPageID | 1145955 (xsd:integer) |
| dbo:wikiPageLength | 9752 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1025784192 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Probabilistic_Turing_machine dbr:Memory_space_(computational_resource) dbr:NP_(complexity) dbr:Nondeterministic_Turing_machine dbr:Nondeterministic_space dbr:Algorithm dbr:Decision_problem dbr:Concatenation dbr:NC_(complexity) dbr:L_(complexity) dbr:Logarithm dbr:Complement_(complexity) dbr:Complexity_class dbr:Computational_complexity_theory dbr:ZPL_(complexity) dbr:P_(complexity) dbr:Propositional_logic dbr:Transitive_closure dbr:Gödel_Prize dbr:Log-space_reduction dbr:Open_problem dbr:Expected_value dbr:First-order_logic dbr:PSPACE dbr:Cem_Say dbr:Directed_graph dbr:RL_(complexity) dbr:Reachability dbr:2-satisfiability dbc:Complexity_classes dbr:AC_(complexity) dbr:Circuit_complexity dbr:RLP_(complexity) dbr:Certificate_(complexity) dbr:Kleene_star dbr:Neil_Immerman dbr:ST-connectivity dbr:Immerman–Szelepcsényi_theorem dbr:Róbert_Szelepcsényi dbr:NL-complete dbr:Savitch's_theorem dbr:Unsolved_problems_in_computer_science dbr:Disjunction dbr:Polynomial-time_algorithm dbr:Deterministic_Turing_machine dbr:Decision_problems dbr:NPSPACE dbr:ZPLP_(complexity) |
| dbp:wikiPageUsesTemplate | dbt:= dbt:Cite_book dbt:Reflist dbt:Tmath dbt:Sans-serif dbt:ComplexityClasses dbt:CZoo dbt:Unsolved |
| dct:subject | dbc:Complexity_classes |
| gold:hypernym | dbr:Class |
| rdf:type | yago:WikicatComplexityClasses yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Group100031264 |
| 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) |
| rdfs:label | NL (تعقيد حسابي) (ar) NL (Complexitat) (ca) NL (Komplexitätsklasse) (de) NL (komplikeco) (eo) NL (clase de complejidad) (es) NL (complexité) (fr) NL (complessità) (it) NL (計算複雑性理論) (ja) NL (복잡도) (ko) NL (complexity) (en) Complexidade NL (pt) Классы L и NL (ru) Класи складності L і NL (uk) NL (複雜度) (zh) |
| owl:sameAs | freebase:NL (complexity) yago-res:NL (complexity) wikidata:NL (complexity) dbpedia-ar:NL (complexity) http://ast.dbpedia.org/resource/NL_(clase_de_complexidá) dbpedia-ca:NL (complexity) dbpedia-de:NL (complexity) dbpedia-eo:NL (complexity) dbpedia-es:NL (complexity) dbpedia-fa:NL (complexity) dbpedia-fr:NL (complexity) dbpedia-he:NL (complexity) dbpedia-it:NL (complexity) dbpedia-ja:NL (complexity) dbpedia-ko:NL (complexity) dbpedia-pt:NL (complexity) dbpedia-ru:NL (complexity) dbpedia-sr:NL (complexity) dbpedia-uk:NL (complexity) dbpedia-vi:NL (complexity) dbpedia-zh:NL (complexity) https://global.dbpedia.org/id/Ka6n |
| prov:wasDerivedFrom | wikipedia-en:NL_(complexity)?oldid=1025784192&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:NL_(complexity) |
| is dbo:knownFor of | dbr:Walter_Savitch |
| is dbo:wikiPageDisambiguates of | dbr:NL |
| is dbo:wikiPageRedirects of | dbr:Nondeterministic_logarithmic_space dbr:Nondeterministic_logspace dbr:ZPL_(complexity) dbr:NLOGSPACE dbr:NLSPACE dbr:Conl-complete dbr:NL_(complexity_class) dbr:NL_(complexity_theory) dbr:Nlog |
| is dbo:wikiPageWikiLink of | dbr:List_of_complexity_classes dbr:List_of_computer_scientists dbr:NL dbr:Nondeterministic_logarithmic_space dbr:Nondeterministic_logspace dbr:Book_embedding dbr:Descriptive_Complexity dbr:Descriptive_complexity_theory dbr:Integer_circuit dbr:Space_hierarchy_theorem dbr:SL_(complexity) dbr:Greatest_common_divisor dbr:NC_(complexity) dbr:Configuration_graph dbr:LOGCFL dbr:L_(complexity) dbr:Complement_(complexity) dbr:Complexity_class dbr:Computational_complexity_theory dbr:ZPL_(complexity) dbr:PL_(complexity) dbr:Many-one_reduction dbr:Transitive_closure dbr:Walter_Savitch dbr:Log-space_reduction dbr:Polynomial-time_reduction dbr:PSPACE dbr:Cem_Say dbr:Isolation_lemma dbr:RL_(complexity) dbr:Reduction_(complexity) dbr:2-satisfiability dbr:State_complexity dbr:Read-only_Turing_machine dbr:Boolean_satisfiability_problem dbr:CC_(complexity) dbr:St-connectivity dbr:Circuits_over_sets_of_natural_numbers dbr:Implicit_graph dbr:Certificate_(complexity) dbr:SC_(complexity) dbr:Sardinas–Patterson_algorithm dbr:FL_(complexity) dbr:Immerman–Szelepcsényi_theorem dbr:List_of_unsolved_problems_in_computer_science dbr:Symmetric_Turing_machine dbr:Finite_model_theory dbr:First-order_reduction dbr:Fixed-point_logic dbr:NSPACE dbr:NLOGSPACE dbr:NLSPACE dbr:NL-complete dbr:Savitch's_theorem dbr:Structural_complexity_theory dbr:Space_complexity dbr:Two-way_finite_automaton dbr:Conl-complete dbr:NL_(complexity_class) dbr:NL_(complexity_theory) dbr:Nlog |
| is dbp:knownFor of | dbr:Walter_Savitch |
| is foaf:primaryTopic of | wikipedia-en:NL_(complexity) |