About: NL (complexity)

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: NL (complexity) Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : fr.dbpedia.org associated with source document(s)

Attributes	Values
rdfs:comment	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)
Wikipage page ID	6928679 (xsd:integer)
dbo:wikiPageWikiLink	dbpedia-fr:21_problèmes_NP-complets_de_Karp First-order logic category-fr:Classe_de_complexité dbpedia-fr:Classe_de_complexité Clause (logic) Descriptive complexity theory Space complexity Transitive closure dbpedia-fr:Graphe_orienté Theoretical computer science dbpedia-fr:L_(complexité) Literal (mathematical logic) dbpedia-fr:Logarithme Nondeterministic Turing machine dbpedia-fr:NC_(complexité) NP (complexity) Neil Immerman dbpedia-fr:PSPACE dbpedia-fr:P_(complexité) dbpedia-fr:Problème_2-SAT dbpedia-fr:Problème_NP-complet dbpedia-fr:Problème_SAT dbpedia-fr:Problème_d'accessibilité dbpedia-fr:Problème_de_décision dbpedia-fr:Réduction_en_espace_logarithmique Róbert Szelepcsényi dbpedia-fr:Théorie_de_la_complexité_(informatique_théorique) Savitch's theorem
page length (characters) of wiki page	8539 (xsd:nonNegativeInteger)
is dbo:wikiPageWikiLink of	dbpedia-fr:Classe_de_complexité Descriptive complexity theory Space complexity State complexity dbpedia-fr:LOGCFL dbpedia-fr:L_(complexité) dbpedia-fr:Liste_de_classes_de_complexité Symmetric Turing machine dbpedia-fr:NC_(complexité) NL NSPACE dbpedia-fr:PSPACE dbpedia-fr:P_(complexité) dbpedia-fr:Problème_2-SAT dbpedia-fr:Problème_de_l'évaluation_d'un_circuit dbpedia-fr:Réduction_en_espace_logarithmique dbpedia-fr:Théorie_de_la_complexité_(informatique_théorique) dbpedia-fr:Théorème_d'Immerman-Szelepcsényi dbpedia-fr:NLOGSPACE dbpedia-fr:Classe_NL dbpedia-fr:Co-NL

Faceted Search & Find service v1.16.111 as of Oct 19 2022

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3234 as of May 18 2022, on Linux (x86_64-ubuntu_bionic-linux-gnu), Single-Server Edition (39 GB total memory, 5 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software