| dbo:abstract
|
- En teoria de la complexitat, la classe de complexitat PolyL és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en un espai fitat per una funció polilogarítmica. Per tant es pot dir que PolyL = DSPACE ((log n)O(1)) on n és la mida de l'entrada i O(1) és una constant. (ca)
- En complejidad computacional, PolyL es una clase de complejidad que contiene aquellos lenguajes para los cuales existe un algoritmo determinista cuyo espacio de decisión requerido está acotado por un polilogaritmo en función del tamaño de la entrada. En otras palabras, polyL = DSPACE((log n)O(1)), donde n denota el tamaño de la entrada, y O(1) es una constante. A diferencia de la clase L, que está contenida en P, no se sabe si polyL esté contenida en P, o viceversa. Por otra parte, sabemos que polyL ≠ P. (es)
- In computational complexity theory, polyL is the complexity class of decision problems that can be solved on a deterministic Turing machine by an algorithm whose space complexity is bounded by a polylogarithmic function in the size of the input. In other words, polyL = DSPACE((log n)O(1)), where n denotes the input size, and O(1) denotes a constant. Just as L ⊆ P, polyL ⊆ QP. However, the only proven relationship between polyL and P is that polyL ≠ P; it is unknown if polyL ⊊ P, if P ⊊ polyL, or if neither is contained in the other. One proof that polyL ≠ P is that P has a complete problem under logarithmic space many-one reductions but polyL does not due to the space hierarchy theorem.The space hierarchy theorem guarantees that DSPACE(logd n) ⊊ DSPACE(logd + 1 n) for all integers d > 0. If polyL had a complete problem, call it A, it would be an element of DSPACE(logk n) for some integer k > 0. Suppose problem B is an element of DSPACE(logk + 1 n) \ DSPACE(logk n). The assumption that A is complete implies the following O(logk n) space algorithm for B: reduce B to A in logarithmic space, then decide A in O(logk n) space. This implies that B is an element of DSPACE(logk n) and hence violates the space hierarchy theorem. (en)
- 在計算複雜度理論內，PolyL是一個決定性問題的複雜度類， 可以使用決定型圖靈機使用被某個輸入大小的多对数函数(polylogarithmic)函数所限制的空間。換句話說，polyL = ((log n)O(1))，這裡的 O(1)代表一個常數。 相對於已知包含在P內的L，我們尚且不知道是否polyL是包含於P內，或者反過來。(PolyL已知包含於QP，或說，(Quasi-polynomial time)之內)。 話說回來，我們知道polyL ≠ P，因為(舉例來說) polyL並沒有在對數空間歸約之下的完備問題。 但是P則有這類問題。PolyL沒有對數空間之下的完備問題是因為(space hierarchy theory)保證了((log n)1) ⊊ DSPACE((log n)2) ⊊ DSPACE((log n)3)…等等。如果polyL有完備問題，則這問題必然落在某個DSPACE((log n)k)內(k為某個常數)。這會令PolyL，也就是包含DSPACE((log n)k+1)以上所有空間複雜度內的問題，全部可以歸約為DSPACE((log n)k)，而違背了空間譜系理論。 (zh)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 1844 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- En teoria de la complexitat, la classe de complexitat PolyL és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en un espai fitat per una funció polilogarítmica. Per tant es pot dir que PolyL = DSPACE ((log n)O(1)) on n és la mida de l'entrada i O(1) és una constant. (ca)
- En complejidad computacional, PolyL es una clase de complejidad que contiene aquellos lenguajes para los cuales existe un algoritmo determinista cuyo espacio de decisión requerido está acotado por un polilogaritmo en función del tamaño de la entrada. En otras palabras, polyL = DSPACE((log n)O(1)), donde n denota el tamaño de la entrada, y O(1) es una constante. A diferencia de la clase L, que está contenida en P, no se sabe si polyL esté contenida en P, o viceversa. Por otra parte, sabemos que polyL ≠ P. (es)
- 在計算複雜度理論內，PolyL是一個決定性問題的複雜度類， 可以使用決定型圖靈機使用被某個輸入大小的多对数函数(polylogarithmic)函数所限制的空間。換句話說，polyL = ((log n)O(1))，這裡的 O(1)代表一個常數。 相對於已知包含在P內的L，我們尚且不知道是否polyL是包含於P內，或者反過來。(PolyL已知包含於QP，或說，(Quasi-polynomial time)之內)。 話說回來，我們知道polyL ≠ P，因為(舉例來說) polyL並沒有在對數空間歸約之下的完備問題。 但是P則有這類問題。PolyL沒有對數空間之下的完備問題是因為(space hierarchy theory)保證了((log n)1) ⊊ DSPACE((log n)2) ⊊ DSPACE((log n)3)…等等。如果polyL有完備問題，則這問題必然落在某個DSPACE((log n)k)內(k為某個常數)。這會令PolyL，也就是包含DSPACE((log n)k+1)以上所有空間複雜度內的問題，全部可以歸約為DSPACE((log n)k)，而違背了空間譜系理論。 (zh)
- In computational complexity theory, polyL is the complexity class of decision problems that can be solved on a deterministic Turing machine by an algorithm whose space complexity is bounded by a polylogarithmic function in the size of the input. In other words, polyL = DSPACE((log n)O(1)), where n denotes the input size, and O(1) denotes a constant. (en)
|
| rdfs:label
|
- PolyL (Complexitat) (ca)
- PolyL (es)
- PolyL (en)
- PolyL (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
