| rdfs:comment
| - En teoria de la complexitat, la classe de complexitat L, també coneguda com a LSPACE o DLOGSPACE, és la classe dels problemes de decisió que es poden resoldre per una màquina de Turing determinista usant una quantitat logarítmica d'espai. Formalment, la màquina de Turing te dues cintes, una per codificar l'entrada i només es pot llegir i l'altra cinta té una mida logarítmica però es pot llegir i escriure. (ca)
- In der Komplexitätstheorie bezeichnet L die Klasse der Entscheidungsprobleme, welche von einer deterministischen Turingmaschine mit logarithmischem Platzverbrauch gelöst werden können. Um logarithmischen Platzverbrauch definieren zu können, muss hierbei vorausgesetzt werden, dass die Eingabe für das Entscheidungsproblem auf einem separaten Eingabeband gegeben ist. Dieses kann nur gelesen werden und wird für die Angabe des Platzverbrauchs nicht berücksichtigt. (de)
- In computational complexity theory, L (also known as LSPACE or DLOGSPACE) is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a logarithmic amount of writable memory space. Formally, the Turing machine has two tapes, one of which encodes the input and can only be read, whereas the other tape has logarithmic size but can be read as well as written. Logarithmic space is sufficient to hold a constant number of pointers into the input and a logarithmic number of boolean flags, and many basic logspace algorithms use the memory in this way. (en)
- W obliczeniowej teorii złożoności L (znane również jako LSPACE lub DLOGSPACE) jest klasą złożoności zawierającą problemy decyzyjne, które można rozwiązać za pomocą deterministycznej maszyny Turinga przy użyciu logarytmicznej ilości zapisywalnej przestrzeni pamięci. Formalnie maszyna Turinga ma dwie taśmy, z których jedna koduje dane wejściowe i może być tylko odczytywana, podczas gdy druga taśma ma rozmiar logarytmiczny, ale można ją czytać i zapisywać. Przestrzeń logarytmiczna jest wystarczająca do przechowywania stałej liczby wskaźników na wejściu i logarytmicznej liczby flag boolowskich, a wiele podstawowych algorytmów pamięci logarytmicznej wykorzystuje w ten sposób pamięć. (pl)
- Em teoria da complexidade, L (também conhecido como LSPACE ou DLOGSPACE) é a classe de complexidade que contém problemas de decisão os quais podem ser resolvidos por uma máquina de Turing utilizando uma quantidade de espaço de memória logarítmico. Espaço logarítmico é suficiente para manter um número constante de apontadores para entrada e um número logarítmico de flags booleanas, e muitos algoritmos básicos logspace utilizam a memória dessa forma. (pt)
- L也稱為LSPACE或DLOGSPACE，是计算复杂度理论中能被确定型图灵机利用對數空间解决的判定问题集合。 对数空间是指与输入规模成对数大小关系的可写的储存空间，大多数对数空间（LOGSPACE）算法以这种方式储存。 重要的相關未解問題包括複雜度類L和P是否恆等（L = P）及複雜度類L和NL是否恆等（L = NL）。目前已知有以下重要性质：
* L ⊆ NL ⊆ P
* NC1 ⊆ L ⊆ NL ⊆ NC2 (zh)
- En , L estas de , kiuj povas esti solvitaj per maŝino de Turing kun uzo de logaritma kvanto de . Intuicie, logaritma spaco estas spaco sufiĉa por konservi konstantan kvanton de nadloj en la enigo kaj logaritman kvanton de buleaj flagoj. Ĝeneraligo de L estas NL, kiu estas klaso de lingvoj decideblaj en logaritma spaco per determinisma maŝino de Turing. Tiam . 'Ĉu L = P ?' kaj 'ĉu L = NL ?' estas gravaj malfermitaj problemoj. La rilatanta klaso de estas . FL estas ofte uzata por difini . (eo)
- En teoría de la complejidad computacional, la clase de complejidad L (LSPACE o espacio logarítmico 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 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 (es)
- 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)
- 계산 복잡도 이론에서 L(LSPACE 또는 DLOGSPACE)은 결정론적 튜링 기계가 로그 기억 공간을 써서 풀 수 있는 판정 문제의 복잡도 종류이다. 로그 공간은 입력에 대한 포인터 상수개와 이진 플래그 로그 개를 담기에 충분하다는 것을 직관으로 알 수 있다. L을 일반화한 것이 NL이다. NL은 비결정론적 튜링 기계가 로그 공간을 써서 판정할 수 있는 언어의 집합이다. L ⊆ NL인 것은 자명하다. 그리고 O(log n) 공간을 쓰는 판정자는 시간을 아무리 많이 써도 가능한 경우의 수인 2O(log n)=nO(1)을 넘지 않는다. 따라서 L ⊆ P가 된다. 여기서 P는 결정론적 다항 시간에 풀 수 있는 문제의 집합이다. 모든 L 문제는 에 대해 완전(complete)하다. 이 환산은 쓸모없기 때문에, L에 들어 있는 더 강한 완전 문제들을 동일시하는 더 약한 환산들이 정의되었다. 그러나 L-완전에 대한 정의 중 일반적으로 쓰이는 것은 없다. 아직 해결되지 않은 문제 중 중요한 것으로 L = P인가 하는 문제와 L = NL인가 하는 문제가 있다. L과 관계 있는 문제로, 함수 문제에 대한 복잡도 종류인 이 있다. FL은 로그 공간 환산을 정의할 때 자주 쓰인다. (ko)
- 計算量理論においてLとは、決定性チューリングマシンで対数規模の領域（メモリ）を使って解くことができる決定問題の集合である。直観的には対数領域は、入力を参照するポインタを一定数保持するのに使われたり、対数個のブール値フラグを保持するのに使われたりする。 Lと関連する計算量にNLがある。NLは、非決定性チューリングマシン上で対数領域で決定可能な言語のクラスである。従って、 が成り立つ。 また、O(log n) の領域を使用する決定機械は時間 2O(log n)=nO(1) 以内で停止するとしてよい。これは、対数領域の機械のとりうる状態の組み合わせの合計である。従って、 が成り立つ。ここで P は決定性チューリングマシンで多項式時間で解ける問題の集合である。 L完全の意味は還元の定め方が難しい。あるLに属する問題がL完全であることを「Lに属するどんな問題も対数領域還元可能であること」と定義すると、Lに属する全ての問題が「L完全」になってしまうので、あまり意味がない。より弱い還元を使う必要がある。 L = P や L = NL が正しいかどうかは未解決である。 関数問題に関する同様の計算量を という。FL は対数領域還元の定義によく使われる。 この結果、L の性質として一階述語論理に推移閉包演算子を追加したもので表される言語が L に含まれることが判明した。 (ja)
- Nella teoria della complessità computazionale, L (nota anche come LSPACE, LOGSPACE o DLOGSPACE) è la classe di complessità che contiene i che possono essere risolti da una macchina di Turing deterministica usando una quantità logaritmica di memoria. Intuitivamente, uno spazio logaritmico è sufficiente a contenere un numero costante di puntatori nell'input, e un numero logaritmico di valori booleani. Problemi aperti importanti sono le questioni ? e ? La classe collegata di problemi costruttivi è . Si usa spesso FL per definire la riduzione in spazio logaritmico. (it)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)