Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/NL_(complexity)> ?p ?o }
Showing triples 1 to 85 of
85
with 100 triples per page.
- NL_(complexity) abstract "In computational complexity theory, NL (Nondeterministic Logarithmic-space) is the complexity class containing decision problems which 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 probabilistic definition below; however, this name is more frequently used to refer to randomized logarithmic space, which is not known to equal NL.".
- NL_(complexity) wikiPageExternalLink l7.ps.
- NL_(complexity) wikiPageID "1145955".
- NL_(complexity) wikiPageLength "7862".
- NL_(complexity) wikiPageOutDegree "52".
- NL_(complexity) wikiPageRevisionID "703584978".
- NL_(complexity) wikiPageWikiLink 2-satisfiability.
- NL_(complexity) wikiPageWikiLink AC_(complexity).
- NL_(complexity) wikiPageWikiLink Algorithm.
- NL_(complexity) wikiPageWikiLink Category:Complexity_classes.
- NL_(complexity) wikiPageWikiLink Circuit_complexity.
- NL_(complexity) wikiPageWikiLink Complement_(complexity).
- NL_(complexity) wikiPageWikiLink Complexity_class.
- NL_(complexity) wikiPageWikiLink Computational_complexity_theory.
- NL_(complexity) wikiPageWikiLink Computational_resource.
- NL_(complexity) wikiPageWikiLink Decision_problem.
- NL_(complexity) wikiPageWikiLink Directed_graph.
- NL_(complexity) wikiPageWikiLink Expected_value.
- NL_(complexity) wikiPageWikiLink First-order_logic.
- NL_(complexity) wikiPageWikiLink Gödel_Prize.
- NL_(complexity) wikiPageWikiLink Immerman–Szelepcsényi_theorem.
- NL_(complexity) wikiPageWikiLink L_(complexity).
- NL_(complexity) wikiPageWikiLink List_of_unsolved_problems_in_computer_science.
- NL_(complexity) wikiPageWikiLink Log-space_reduction.
- NL_(complexity) wikiPageWikiLink Logarithm.
- NL_(complexity) wikiPageWikiLink Logical_disjunction.
- NL_(complexity) wikiPageWikiLink Michael_Sipser.
- NL_(complexity) wikiPageWikiLink NC_(complexity).
- NL_(complexity) wikiPageWikiLink NL-complete.
- NL_(complexity) wikiPageWikiLink NL_(complexity).
- NL_(complexity) wikiPageWikiLink NSPACE.
- NL_(complexity) wikiPageWikiLink Neil_Immerman.
- NL_(complexity) wikiPageWikiLink Non-deterministic_Turing_machine.
- NL_(complexity) wikiPageWikiLink Open_problem.
- NL_(complexity) wikiPageWikiLink PSPACE.
- NL_(complexity) wikiPageWikiLink P_(complexity).
- NL_(complexity) wikiPageWikiLink Probabilistic_Turing_machine.
- NL_(complexity) wikiPageWikiLink RL_(complexity).
- NL_(complexity) wikiPageWikiLink Reachability.
- NL_(complexity) wikiPageWikiLink Róbert_Szelepcsényi.
- NL_(complexity) wikiPageWikiLink Savitchs_theorem.
- NL_(complexity) wikiPageWikiLink St-connectivity.
- NL_(complexity) wikiPageWikiLink Time_complexity.
- NL_(complexity) wikiPageWikiLink Transitive_closure.
- NL_(complexity) wikiPageWikiLink Turing_machine.
- NL_(complexity) wikiPageWikiLink ZPLP_(complexity).
- NL_(complexity) wikiPageWikiLinkText "'''NL'''".
- NL_(complexity) wikiPageWikiLinkText "L = NL problem".
- NL_(complexity) wikiPageWikiLinkText "NL (complexity)".
- NL_(complexity) wikiPageWikiLinkText "NL (complexity)#Probabilistic definition".
- NL_(complexity) wikiPageWikiLinkText "NL".
- NL_(complexity) wikiPageWikiLinkText "NL_(complexity)".
- NL_(complexity) wikiPageWikiLinkText "logarithmic space".
- NL_(complexity) wikiPageWikiLinkText "nondeterministic logarithmic space".
- NL_(complexity) wikiPageUsesTemplate Template:=.
- NL_(complexity) wikiPageUsesTemplate Template:As_of.
- NL_(complexity) wikiPageUsesTemplate Template:CZoo.
- NL_(complexity) wikiPageUsesTemplate Template:Cite_book.
- NL_(complexity) wikiPageUsesTemplate Template:ComplexityClasses.
- NL_(complexity) wikiPageUsesTemplate Template:Unsolved.
- NL_(complexity) subject Category:Complexity_classes.
- NL_(complexity) hypernym Class.
- NL_(complexity) type Class.
- NL_(complexity) type Page.
- NL_(complexity) comment "In computational complexity theory, NL (Nondeterministic Logarithmic-space) is the complexity class containing decision problems which 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.".
- NL_(complexity) label "NL (complexity)".
- NL_(complexity) sameAs Q12857599.
- NL_(complexity) sameAs NL_(clase_de_complexidá).
- NL_(complexity) sameAs NL_(Komplexitätsklasse).
- NL_(complexity) sameAs NL_(komplikeco).
- NL_(complexity) sameAs NL_(clase_de_complejidad).
- NL_(complexity) sameAs NL_(complexité).
- NL_(complexity) sameAs NL_(סיבוכיות).
- NL_(complexity) sameAs NL_(complessità).
- NL_(complexity) sameAs NL_(計算複雑性理論).
- NL_(complexity) sameAs NL_(복잡도).
- NL_(complexity) sameAs Complexidade_NL.
- NL_(complexity) sameAs m.04b7_8.
- NL_(complexity) sameAs Классы_L_и_NL.
- NL_(complexity) sameAs NL_(сложеност).
- NL_(complexity) sameAs NL_(độ_phức_tạp).
- NL_(complexity) sameAs Q12857599.
- NL_(complexity) sameAs NL_(複雜度).
- NL_(complexity) wasDerivedFrom NL_(complexity)?oldid=703584978.
- NL_(complexity) isPrimaryTopicOf NL_(complexity).