| Property |
Value |
| dbo:abstract
|
- En informatique théorique, et notamment dans la théorie de la complexité, la classe L est la classe des problèmes de décision décidés par une machine de Turing déterministe qui utilise un espace de taille logarithmique en fonction de la taille de l'entrée. Pour être plus précis, l'exigence sur l'espace de taille logarithmique se réfère à l'espace supplémentaire utilisable. Elle est aussi parfois notée LOGSPACE[réf. nécessaire]. Intuitivement, cette classe contient les problèmes que l'on peut décider avec un nombre constant de pointeurs sur des cases mémoires de l'entrée du problème et un nombre constant de données supplémentaires (des compteurs dont les valeurs sont entre 0 et une grandeur polynomiale en la taille de l'entrée, des booléens, etc.). (fr)
- En informatique théorique, et notamment dans la théorie de la complexité, la classe L est la classe des problèmes de décision décidés par une machine de Turing déterministe qui utilise un espace de taille logarithmique en fonction de la taille de l'entrée. Pour être plus précis, l'exigence sur l'espace de taille logarithmique se réfère à l'espace supplémentaire utilisable. Elle est aussi parfois notée LOGSPACE[réf. nécessaire]. Intuitivement, cette classe contient les problèmes que l'on peut décider avec un nombre constant de pointeurs sur des cases mémoires de l'entrée du problème et un nombre constant de données supplémentaires (des compteurs dont les valeurs sont entre 0 et une grandeur polynomiale en la taille de l'entrée, des booléens, etc.). (fr)
|
| dbo:isPartOf
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 10405 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1979 (xsd:integer)
- 1993 (xsd:integer)
- 1997 (xsd:integer)
- 2004 (xsd:integer)
- 2008 (xsd:integer)
|
| prop-fr:doi
| |
| prop-fr:fin
|
- L#l (fr)
- S#sl (fr)
- L#l (fr)
- S#sl (fr)
|
| prop-fr:isbn
| |
| prop-fr:journal
| |
| prop-fr:langue
| |
| prop-fr:lienAuteur
|
- Christos Papadimitriou (fr)
- Michael Sipser (fr)
- David S. Johnson (fr)
- Michael Garey (fr)
- Omer Reingold (fr)
- Christos Papadimitriou (fr)
- Michael Sipser (fr)
- David S. Johnson (fr)
- Michael Garey (fr)
- Omer Reingold (fr)
|
| prop-fr:lieu
|
- New York (fr)
- Reading (fr)
- New York (fr)
- Reading (fr)
|
| prop-fr:mr
| |
| prop-fr:nom
|
- L (fr)
- Johnson (fr)
- SL (fr)
- Papadimitriou (fr)
- Reingold (fr)
- Sipser (fr)
- Garey (fr)
- L (fr)
- Johnson (fr)
- SL (fr)
- Papadimitriou (fr)
- Reingold (fr)
- Sipser (fr)
- Garey (fr)
|
| prop-fr:numéro
|
- 4 (xsd:integer)
- 94 (xsd:integer)
|
| prop-fr:numéroChapitre
| |
| prop-fr:numéroD'édition
| |
| prop-fr:pages
| |
| prop-fr:pagesTotales
|
- 338 (xsd:integer)
- 396 (xsd:integer)
- 523 (xsd:integer)
|
| prop-fr:passage
|
- Chapter 16: Logarithmic space, pp. 395–408 (fr)
- Section 7.5: Logarithmic Space, pp. 177–181 (fr)
- Section 8.4: The Classes L and NL, pp. 294–296 (fr)
- Chapter 16: Logarithmic space, pp. 395–408 (fr)
- Section 7.5: Logarithmic Space, pp. 177–181 (fr)
- Section 8.4: The Classes L and NL, pp. 294–296 (fr)
|
| prop-fr:prénom
|
- Michael (fr)
- Christos (fr)
- Omer (fr)
- D.S. (fr)
- M.R. (fr)
- Michael (fr)
- Christos (fr)
- Omer (fr)
- D.S. (fr)
- M.R. (fr)
|
| prop-fr:sousTitre
|
- a guide to the theory of NP-completeness (fr)
- a guide to the theory of NP-completeness (fr)
|
| prop-fr:titre
|
- Computational Complexity (fr)
- Computers and intractability (fr)
- Introduction to the Theory of Computation (fr)
- Undirected ST-connectivity in Log-Space (fr)
- Undirected connectivity in log-space (fr)
- Computational Complexity (fr)
- Computers and intractability (fr)
- Introduction to the Theory of Computation (fr)
- Undirected ST-connectivity in Log-Space (fr)
- Undirected connectivity in log-space (fr)
|
| prop-fr:titreChapitre
|
- The computational model —and why it doesn’t matter (fr)
- The computational model —and why it doesn’t matter (fr)
|
| prop-fr:url
| |
| prop-fr:volume
| |
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
|
- Addison Wesley (fr)
- W.H. Freeman (fr)
- PWS Publishing (fr)
- Addison Wesley (fr)
- W.H. Freeman (fr)
- PWS Publishing (fr)
|
| dct:subject
| |
| rdfs:comment
|
- En informatique théorique, et notamment dans la théorie de la complexité, la classe L est la classe des problèmes de décision décidés par une machine de Turing déterministe qui utilise un espace de taille logarithmique en fonction de la taille de l'entrée. Pour être plus précis, l'exigence sur l'espace de taille logarithmique se réfère à l'espace supplémentaire utilisable. Elle est aussi parfois notée LOGSPACE[réf. nécessaire]. (fr)
- En informatique théorique, et notamment dans la théorie de la complexité, la classe L est la classe des problèmes de décision décidés par une machine de Turing déterministe qui utilise un espace de taille logarithmique en fonction de la taille de l'entrée. Pour être plus précis, l'exigence sur l'espace de taille logarithmique se réfère à l'espace supplémentaire utilisable. Elle est aussi parfois notée LOGSPACE[réf. nécessaire]. (fr)
|
| rdfs:label
|
- L (Komplexitätsklasse) (de)
- L (clase de complejidad) (es)
- L (complexitat) (ca)
- L (complexité) (fr)
- L (複雜度) (zh)
- L (計算複雑性理論) (ja)
- L (Komplexitätsklasse) (de)
- L (clase de complejidad) (es)
- L (complexitat) (ca)
- L (complexité) (fr)
- L (複雜度) (zh)
- L (計算複雑性理論) (ja)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
