| dbo:abstract
|
- En teoria de la complexitat, la classe de complexitat SC (classe de Steve, per Stephen Cook) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en temps polinòmic (classe P) i en espai polilogarítmic (classe PolyL) O((log n)k per una constant k. La definició de la classe SC és diferent de P ∩ PolyL, ja que la classe SC es requereix que un algorisme compleixi les dues restriccions juntes i per la intersecció dos algorismes separats és suficient, un algorisme funciona en temps polinòmic i un segon algorisme funciona en espai polilogarítmic. (ca)
- En informatique théorique, plus précisément en théorie de la complexité, SC est la classe de complexité des problèmes de décision, décidés par un algorithme en temps polynomial et en espace polylogarithmique.
* Portail de l'informatique théorique (fr)
- En complejidad computacional, SC (Steve's Class, en español Clase de Steve en honor a Stephen Cook) es una clase de complejidad que incluye a los problemas resolubles por una máquina de Turing determinista en tiempo polinomial (clase P) y espacio polilogarítmico (clase PolyL) (esto es un espacio de orden O(logk n) para alguna constante k). También es llamada DTISP(poly, polylog), donde DTISP significa deterministic time and space ("tiempo y espacio determinista"). Note que la clase SC está contenida estrictamente en la clase P ∩ PolyL, puesto que para la primera, se requiere que el algoritmo corra al mismo tiempo en tiempo polinomial y espacio polilogarítmico; mientras que para la segunda, dos algoritmos posiblemente distintos pueden separadamente satisfacer ambas condiciones. Cook demostró en 1979 que los deterministas, reconocidos por los autómatas con pila deterministas, están contenidos en SC. Las clases y contienen problemas aceptables por máquinas de Turing probabilísticas en espacio logarítmico y tiempo polinomial. Nisan demostró en 1992 que ambas clases están contenidas en SC. En otras palabras, dado un espacio polilogarítmico, una máquina determinista puede simular un algoritmo probabilista de espacio logarítmico. (es)
- In computational complexity theory, SC (Steve's Class, named after Stephen Cook) is the complexity class of problems solvable by a deterministic Turing machine in polynomial time (class P) and polylogarithmic space (class PolyL) (that is, O((log n)k) space for some constant k). It may also be called DTISP(poly, polylog), where DTISP stands for deterministic time and space. Note that the definition of SC differs from P ∩ PolyL, since for the former, it is required that a single algorithm runs in both polynomial time and polylogarithmic space; while for the latter, two separate algorithms will suffice: one that runs in polynomial time, and another that runs in polylogarithmic space. (It is unknown whether SC and P ∩ PolyL are equivalent). DCFL, the strict subset of context-free languages recognized by deterministic pushdown automata, is contained in SC, as shown by Cook in 1979. It is open if all context-free languages can be recognized in SC, although they are known be in P ∩ PolyL. It is open if directed st-connectivity is in SC, although it is known to be in P ∩ PolyL (because of a DFS algorithm and Savitch's theorem). This question is equivalent to NL ⊆ SC. RL and BPL are classes of problems acceptable by probabilistic Turing machines in logarithmic space and polynomial time. Noam Nisan showed in 1992 the weak derandomization result that both are contained in SC. In other words, given polylogarithmic space, a deterministic machine can simulate logarithmic space probabilistic algorithms. (en)
- Na teoria da complexidade computacional, SC (Steve Classe, em homenagem a Stephen Cook) é a classe de complexidade dos problemas resolvidos por uma máquina de Turing determinística em tempo polinomial (classe P) e em espaço espaço polylogarithmic (classe PolyL) (isto é, O((log n)k) espaço para alguma constante k). Ele também pode ser chamado DTISP(poli, polylog), onde DTISP significa determinística do tempo e do espaço. Note que a definição de SC é diferente de P ∩ PolyL, uma vez que, para os antigos, é necessário que o algoritmo é executado tanto em tempo polinomial e polylogarithmic espaço; enquanto que para o último, dois algoritmos será suficiente: um que é executado em tempo polinomial, e outro que é executado no polylogarithmic espaço. (Não se sabe se o PB e P ∩ PolyL são equivalentes). DCFL, o subconjunto estrito de linguagens livre de contexto reconhecido pelo "deterministic pushdown automata", está contido em SC, como mostrado por Cook em 1979. É abrir-se dirigido st-conectividade é em SC, embora seja conhecido na P ∩ PolyL (por causa de um algoritmo DFS e o teorema de Savitch). Esta pergunta é equivalente a NL ⊆ SC. RL e BPL são classes de problemas aceitável por máquinas de Turing probabilística em logarítmica espaço e tempo polinomial. Noam Nissan mostrou, em 1992, o fraco resultado conhecido como derandomization ("desrandomização") indica que ambos estão contidos em SC. Em outras palavras, dada espaço polylogarithmic, um determinista da máquina pode simular logarítmica espaço probabilístico de algoritmos. (pt)
- 在計算複雜度理論內，SC (Steve's Class，以史蒂芬·库克命名)是一個複雜度類，包含了使用圖靈機，在多項式時間(P複雜度類)以及多項式對數空間(PolyL複雜度類) (也就是，O(logk n)空間，k是某個常數)。我們也可以稱呼這個複雜度類為DTISP(poly, polylog)，這裡DTISP代表確定性時間與空間(deterministic time and space)。這裡的SC是P PolyL的嚴格子集，因為對前者，他需要存在一個解決問題的演算法同時滿足多項式時間以及多項式對數空間兩個條件；而對後者這個聯集來說，他只需要兩個各自的演算法，其中一個是多項式時間，另一個是多項式對數空間即可以滿足。 ，這個複雜度類是上下文無關語言的子集，使用確定下推自動機來驗證。DCFL已知是包含在SC內的，由Cook在1979年證明。 RL和BPL是能夠以概率圖靈機在多項式時間和多項式對數空間解決的複雜度類。Nisan在1992年證明了一個較弱的，因此可以證明這兩個複雜度類都在SC裡面。換句話說，給出一個多項式對數空間，我們可以用一個確定型的圖靈機來模擬 對數空間的機率演算法。 (zh)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 2728 (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 SC (classe de Steve, per Stephen Cook) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en temps polinòmic (classe P) i en espai polilogarítmic (classe PolyL) O((log n)k per una constant k. La definició de la classe SC és diferent de P ∩ PolyL, ja que la classe SC es requereix que un algorisme compleixi les dues restriccions juntes i per la intersecció dos algorismes separats és suficient, un algorisme funciona en temps polinòmic i un segon algorisme funciona en espai polilogarítmic. (ca)
- En informatique théorique, plus précisément en théorie de la complexité, SC est la classe de complexité des problèmes de décision, décidés par un algorithme en temps polynomial et en espace polylogarithmique.
* Portail de l'informatique théorique (fr)
- 在計算複雜度理論內，SC (Steve's Class，以史蒂芬·库克命名)是一個複雜度類，包含了使用圖靈機，在多項式時間(P複雜度類)以及多項式對數空間(PolyL複雜度類) (也就是，O(logk n)空間，k是某個常數)。我們也可以稱呼這個複雜度類為DTISP(poly, polylog)，這裡DTISP代表確定性時間與空間(deterministic time and space)。這裡的SC是P PolyL的嚴格子集，因為對前者，他需要存在一個解決問題的演算法同時滿足多項式時間以及多項式對數空間兩個條件；而對後者這個聯集來說，他只需要兩個各自的演算法，其中一個是多項式時間，另一個是多項式對數空間即可以滿足。 ，這個複雜度類是上下文無關語言的子集，使用確定下推自動機來驗證。DCFL已知是包含在SC內的，由Cook在1979年證明。 RL和BPL是能夠以概率圖靈機在多項式時間和多項式對數空間解決的複雜度類。Nisan在1992年證明了一個較弱的，因此可以證明這兩個複雜度類都在SC裡面。換句話說，給出一個多項式對數空間，我們可以用一個確定型的圖靈機來模擬 對數空間的機率演算法。 (zh)
- En complejidad computacional, SC (Steve's Class, en español Clase de Steve en honor a Stephen Cook) es una clase de complejidad que incluye a los problemas resolubles por una máquina de Turing determinista en tiempo polinomial (clase P) y espacio polilogarítmico (clase PolyL) (esto es un espacio de orden O(logk n) para alguna constante k). También es llamada DTISP(poly, polylog), donde DTISP significa deterministic time and space ("tiempo y espacio determinista"). Note que la clase SC está contenida estrictamente en la clase P ∩ PolyL, puesto que para la primera, se requiere que el algoritmo corra al mismo tiempo en tiempo polinomial y espacio polilogarítmico; mientras que para la segunda, dos algoritmos posiblemente distintos pueden separadamente satisfacer ambas condiciones. (es)
- In computational complexity theory, SC (Steve's Class, named after Stephen Cook) is the complexity class of problems solvable by a deterministic Turing machine in polynomial time (class P) and polylogarithmic space (class PolyL) (that is, O((log n)k) space for some constant k). It may also be called DTISP(poly, polylog), where DTISP stands for deterministic time and space. Note that the definition of SC differs from P ∩ PolyL, since for the former, it is required that a single algorithm runs in both polynomial time and polylogarithmic space; while for the latter, two separate algorithms will suffice: one that runs in polynomial time, and another that runs in polylogarithmic space. (It is unknown whether SC and P ∩ PolyL are equivalent). (en)
- Na teoria da complexidade computacional, SC (Steve Classe, em homenagem a Stephen Cook) é a classe de complexidade dos problemas resolvidos por uma máquina de Turing determinística em tempo polinomial (classe P) e em espaço espaço polylogarithmic (classe PolyL) (isto é, O((log n)k) espaço para alguma constante k). Ele também pode ser chamado DTISP(poli, polylog), onde DTISP significa determinística do tempo e do espaço. Note que a definição de SC é diferente de P ∩ PolyL, uma vez que, para os antigos, é necessário que o algoritmo é executado tanto em tempo polinomial e polylogarithmic espaço; enquanto que para o último, dois algoritmos será suficiente: um que é executado em tempo polinomial, e outro que é executado no polylogarithmic espaço. (Não se sabe se o PB e P ∩ PolyL são equivalente (pt)
|
| rdfs:label
|
- SC (Complexitat) (ca)
- SC (clase de complejidad) (es)
- SC (complexité) (fr)
- SC (complexity) (en)
- SC (complexidade) (pt)
- SC (複雜度) (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
