| dbo:abstract
|
- 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)
- 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 . P estas minimume same granda kiel , la klaso de problemoj decidebla en logaritma kvanto de . Kun uzo de spaco O(log n) ne povas esti uzata tempo pli grandan ol 2O(log n) = nO(1), ĉar ĉi tio estas la entuta kvanto de eblaj konfiguroj, konservataj en la memoro. Poste ĉi tia kvanto de paŝoj la algoritmo devas nepre aŭ finiĝi aŭ ripetiĝi de iu jam estinta stato kaj tiel neniam finiĝi. Tial, L estas subaro de P. Ne estas sciata, ĉu L = P. 'Ĉu L = P ?' kaj 'ĉu L = NL ?' estas gravaj malfermitaj problemoj. Plua klasifio de problemoj en L - kiel pli forte plenaj aŭ pli forte plenaj en L - estas interesa. Ĉiu problemo en L estas plena sub . Tiel pro tio ke log-spaca malpligrandiĝo estas ne taŭga, pli malfortaj malpligrandiĝoj estas difinitaj. Sed tamen ne estas ĝenerale akceptita difino de L-pleneco. La rilatanta klaso de estas . FL estas ofte uzata por difini . Omer Reingold en oktobro de 2004 montris, ke USTCON, la problemo de 'ĉu tie ekzistas vojo inter du verticoj en donita sendirekta grafeo?' (vd. st-connectivity), estas en L, kaj do L = , ĉar la problemo estas SL-plena. Unu konsekvenco de ĉi tio estas simpla logika karakterizado de L: ĝi enhavas precize tiuj lingvoj kiuj estas esprimeblaj en kun aldonita komuta operatoro (en grafeteoriaj terminoj, ĉi tiu operatoro reformigas ĉiun en klikon). L estas por sin, ĉar ĝi povas simuli log-spacaj orakolajn demandojn (malglate parolante, "funkciajn vokojn kiu uzas logaritman spacon") en logaritma spaco, reuzanta la saman spacon por ĉiu demando. (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 P es diferente de NP o bien NP es diferente de PSPACE, pero no se sabe cual de las dos inclusiones es propia. (es)
- 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)
- 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)
- 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. Una generalizzazione di L è NL, la classe dei linguaggi decidibili in spazio logaritmico da una macchina di Turing non deterministica. Banalmente si può dire che . Inoltre, un decisore che usa spazio non può impiegare un tempo superiore a , poiché questo è il numero totale di possibili configurazioni; quindi, , dove P è la classe di problemi risolvibili in tempo polinomiale da una macchina di Turing deterministica. Ogni problema in L è completo nella riduzione in spazio logaritmico; dato che ciò risulta inutile, sono state definite riduzioni più deboli che permettono l'identificazione di problemi completi in L in modo più forte, ma non c'è una definizione universalmente accettata di problema L-completo. Problemi aperti importanti sono le questioni ? e ? La classe collegata di problemi costruttivi è . Si usa spesso FL per definire la riduzione in spazio logaritmico. Nell'ottobre 2004, in un articolo ha dimostrato che il problema di stabilire se c'è un percorso tra due vertici in un grafo non direzionato appartiene alla classe L, dimostrando che L = , poiché tale problema è SL-completo. Come conseguenza di ciò, si ha una caratterizzazione logica semplice di L: contiene esattamente quei linguaggi esprimibili in logica del primo ordine con l'aggiunta di un operatore commutativo di (in termini di teoria dei grafi, ciò trasforma ogni componente connesso in una cricca). (it)
- 계산 복잡도 이론에서 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은 로그 공간 환산을 정의할 때 자주 쓰인다. 2004년 10월에 가 발표한 획기적인 논문에 따르면, 주어진 무향 그래프의 두 꼭짓점 사이에 길이 있는가 하는 문제인 USTCON은 L이다. 이 결과는 L = 라는 것을 뜻한다. USTCON은 SL-완전이기 때문이다. 이 결과로 L의 논리적 특징이 하나 도출된다. L은 에 교환 가능한 연산자를 덧붙여 표현할 수 있는 언어의 집합과 똑같다는 것이다. L 자신은 이다. 로그 공간 신탁 질의(대강 말해서, 로그 공간을 쓰는 함수 호출)를 로그 공간만 써서 시뮬레이트할 수 있기 때문이다. 이때 로그 공간만 쓰기 위해서 질의마다 같은 공간을 재활용한다. (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 は対数領域還元の定義によく使われる。 2004年10月、Omer Reingold は論文で USTCON 問題が L に属することを示した。USTCON問題とは、無向グラフで与えられた2点間の経路があるかどうかを判定する問題である。USTCON問題は、SLに属しSL完全であるため、L = SL であることが確定した。 この結果、L の性質として一階述語論理に推移閉包演算子を追加したもので表される言語が L に含まれることが判明した。 L は対数領域の神託（おおまかに言えば、対数領域を使う関数呼び出しに相当）を対数領域でシミュレート可能であり、各問合せに同じ領域を使用する。この性質をLがLに対して low であるという。 (ja)
- 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)
|
| 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)
|
