| rdfs:comment
| - En teoria de la complexitat, la classe de complexitat P-complet és el conjunt dels problemes de decisió que, estant a la classe P, altres problemes de P es poden reduir a ell en un temps polinòmic. Es pot veure aquesta classe com el conjunt de problemes de P que probablement no es poden resoldre eficientment per un computador paral·lel. El problema més bàsic que pertany a P-complet és el següent: donada una màquina de Turing, una entrada i un enter T en notació unària, determinar si la màquina es para en els primers T passos. (ca)
- 계산 복잡도 이론에서 복잡도 종류 P-완전은 판정 문제의 집합으로, 병렬 컴퓨터가 빠르게 풀 수 있는 문제들을 분석하는 데 쓸모가 있다. 어떤 판정 문제가 P-완전이려면 P에 대해 해야 한다. 이는 P에 들어 있는 모든 문제가 프로세스 다항 개가 있는 병렬 컴퓨터로 다항로그 시간을 써서 이 문제로 환산될 수 있다는 뜻이다. 다시 말해서, 어떤 문제 A가 P-완전이려면 P 문제 B마다 B가 A로 병렬 프로세서(nk)개 써서 O((log n)c) 시간에 환산될 수 있는 상수 c와 k가 있다는 뜻이다. 병렬 프로세서의 정의는 NC를 참고하라. (ko)
- 在計算複雜度理論內，標示了P-完全的決定型問題對於分析 1.
* 哪些問題很難有效的平行處理， 2.
* 哪些問題很難在有限空間內解決掉。 相當的有用。 更正式的說，一個決定型問題是P-完全(一個P裡面的完全問題)：若這問題本身在P裡面，且所有在P內的問題，都可以化約為此問題。 特定的化約方式會產生使用差異而且會影響問題集合的大小。 若我們使用NC的化約，亦即，可以在內，以平行運作的電腦在多項式個數之內的處理器下完成的化約，基於一個未被證明的假設 NC ≠ P，則我們可知所有的P-完全問題在NC之外，因此無法被有效率的平行處理化。如果我們使用比較弱的 ，前面的說法維持為真，但是多了一個P-完全問題會在L之外的推論， 基於另一個較弱的，尚未被證明的假設L ≠ P。這裡需要注意到根據後者定義出的P-完全 會是一個比前者小一點的集合。 (zh)
- En teoría de la complejidad computacional, la clase de complejidad P-completo es un conjunto de problemas de decisión de gran utilidad para identificar los problemas que pueden ser resueltos eficientemente en máquinas paralelas. Un problema de decisión está en P-completo si está en NP y todo problema de P puede ser reducido a él en tiempo polilogarítmico en una máquina paralela con un número polinómico de procesadores. En otras palabras, un problema A está en P-completo si para todo problema B en P, existen constantes c y k tales que B puede ser reducido en A en tiempo O((log n)c) utilizando O(nk) procesadores paralelos. En NC se da una definición de procesador paralelo. (es)
- In computational complexity theory, a decision problem is P-complete (complete for the complexity class P) if it is in P and every problem in P can be reduced to it by an appropriate reduction. The notion of P-complete decision problems is useful in the analysis of:
* which problems are difficult to parallelize effectively,
* which problems are difficult to solve in limited space. specifically when stronger notions of reducibility than polytime-reducibility are considered. (en)
- Na teoria da complexidade computacional, a noção de problema de decisão P-completo é útil na análise de questões como: 1.
* que problemas são difíceis de paralelizar eficientemente, e; 2.
* que problemas são difíceis de resolver com espaço limitado. Formalmente, um problema de decisão é P-completo (completo para a classe P de complexidade) se ele está em P e se qualquer problema em P é redutível a ele usando uma função de redução adequada. (pt)
|
| has abstract
| - En teoria de la complexitat, la classe de complexitat P-complet és el conjunt dels problemes de decisió que, estant a la classe P, altres problemes de P es poden reduir a ell en un temps polinòmic. Es pot veure aquesta classe com el conjunt de problemes de P que probablement no es poden resoldre eficientment per un computador paral·lel. El problema més bàsic que pertany a P-complet és el següent: donada una màquina de Turing, una entrada i un enter T en notació unària, determinar si la màquina es para en els primers T passos. (ca)
- En teoría de la complejidad computacional, la clase de complejidad P-completo es un conjunto de problemas de decisión de gran utilidad para identificar los problemas que pueden ser resueltos eficientemente en máquinas paralelas. Un problema de decisión está en P-completo si está en NP y todo problema de P puede ser reducido a él en tiempo polilogarítmico en una máquina paralela con un número polinómico de procesadores. En otras palabras, un problema A está en P-completo si para todo problema B en P, existen constantes c y k tales que B puede ser reducido en A en tiempo O((log n)c) utilizando O(nk) procesadores paralelos. En NC se da una definición de procesador paralelo. Generalmente se admite que la clase P contiene todos los problemas "resolubles" por una máquina secuencial y contiene la clase NC, que consiste en aquellos problemas que se pueden resolver eficientemente en una máquina paralela. Esto se debe a que las máquinas paralelas pueden simularse con máquinas secuenciales. No se sabe si NC=P. En otras palabras, no se sabe si existen problemas resolubles que son inherentemente secuenciales. Como generalmente se acepta que P no es igual a NP, generalmente se acepta también que NC y P son distintos. La clase NP-completo, que puede verse como la que contiene los problemas que probablemente no son resolubles eficientemente, fue introducida para analizar el problema P=NP, y la clase P-completo, que contiene los problemas "probablemente no paralelizables" o "probablemente inherentemente secuenciales" se utiliza igualmente para estudiar la pregunta NC=P. Si se encontrase una forma eficiente de paralelizar la solución de un problema P-completo se echaría por tierra la hipótesis de que NC y P son distintos. El más básico problema P-completo es este: dada una máquina de Turing, una entrada para esa máquina y un entero T (escrito en ), determinar si la máquina se para en los primeros T pasos. Queda claro que el problema es P-completo: Si se pudiera paralelizar una simulación general de una máquina secuencial, se tendría un método general para paralelizar cualquier programa que corre en esa máquina. Si este problema está en NC, todo problema de P también estaría en NC. Este problema ilustra una técnica común utilizada en la teoría de la P-completitud. El interés no está realmente en saber si un problema se puede resolver rápidamente en una máquina paralela. Solo interesa saber si la máquina paralela lo puede resolver muchísimo más rápidamente que la máquina secuencial. Por tanto, el problema también se puede replantear para que la versión secuencial esté en P. Es por ello que en este problema se requiere que T esté escrito en unario. Si un número 'T está escrito como un número , el algoritmo secuencial más obvio puede tomar tiempo 2n. En cambio, si T está escrito como un número unario (una cadena de n unos, para n=T), solo toma tiempo n. Al escribir T en unario en lugar de binario, se reduce el algoritmo obviamente secuencial de tiempo exponencial a lineal, lo cual coloca el problema en la categoría P. Por tanto estará en NC si y solo si es paralelizable. Se ha probado que muchos otros problemas son P-completos y por tanto es una idea generalmente aceptada que se trata de los problemas inherentemente secuenciales. Los siguientes problemas están en P-completo, sea tal y como están expresados, sea transformándolos a la forma de un problema de decisión:
* Problema del valor de una compuerta en un circuito (Circuit Value Problem o CVP) - Dado un , sus entradas y una compuerta lógica en el circuito, calcular la salida de la puerta
* CVP restringido- Igual al anterior, excepto que cada compuerta tiene dos entradas y dos salidas (F y su negación), el resto son compuertas NAND, la entrada de una compuerta viene de la capa inmediatamente anterior
* Programación lineal - Maximizar una función lineal sujeta a restricciones expresadas como desigualdades
* Búsqueda ordenada en profundidad - Dado un grafo con adyacencias fijas ordenadas, y dos nodos u y v, saber si el nodo u será visitado antes del nodo v en una búsqueda en profundidad
* Pertenencia a una gramática libre de contexto - Dado una gramática libre de contexto y una palabra, saber si la palabra pertenece al lenguaje generado por la gramática
* Juego de la vida - Dado una configuración general del juego de la vida de John Conway, una celda particular, y un entero T (en notación unaria), ¿estará la celda viva luego de T pasos? Para demostrar que un problema es P-completo, típicamente se intenta reducir a un problema P-completo, utilizando un algoritmo paralelo eficiente. Existen problemas que no han podido ser clasificados ni en P ni en NP-completo. Uno de ellos es el problema de . Similarmente existen problemas que no se sabe si están en NC o en P-completo, pero que se piensa que son difíciles de paralelizar. Uno de ellos es el problema de decisión asociado al máximo común divisor de dos enteros en notación binaria. (es)
- In computational complexity theory, a decision problem is P-complete (complete for the complexity class P) if it is in P and every problem in P can be reduced to it by an appropriate reduction. The notion of P-complete decision problems is useful in the analysis of:
* which problems are difficult to parallelize effectively,
* which problems are difficult to solve in limited space. specifically when stronger notions of reducibility than polytime-reducibility are considered. The specific type of reduction used varies and may affect the exact set of problems. Generically, reductions stronger than polynomial-time reductions are used, since all languages in P (except the empty language and the language of all strings) are P-complete under polynomial-time reductions. If we use NC reductions, that is, reductions which can operate in polylogarithmic time on a parallel computer with a polynomial number of processors, then all P-complete problems lie outside NC and so cannot be effectively parallelized, under the unproven assumption that NC ≠ P. If we use the stronger log-space reduction, this remains true, but additionally we learn that all P-complete problems lie outside L under the weaker unproven assumption that L ≠ P. In this latter case the set P-complete may be smaller. (en)
- 계산 복잡도 이론에서 복잡도 종류 P-완전은 판정 문제의 집합으로, 병렬 컴퓨터가 빠르게 풀 수 있는 문제들을 분석하는 데 쓸모가 있다. 어떤 판정 문제가 P-완전이려면 P에 대해 해야 한다. 이는 P에 들어 있는 모든 문제가 프로세스 다항 개가 있는 병렬 컴퓨터로 다항로그 시간을 써서 이 문제로 환산될 수 있다는 뜻이다. 다시 말해서, 어떤 문제 A가 P-완전이려면 P 문제 B마다 B가 A로 병렬 프로세서(nk)개 써서 O((log n)c) 시간에 환산될 수 있는 상수 c와 k가 있다는 뜻이다. 병렬 프로세서의 정의는 NC를 참고하라. (ko)
- Na teoria da complexidade computacional, a noção de problema de decisão P-completo é útil na análise de questões como: 1.
* que problemas são difíceis de paralelizar eficientemente, e; 2.
* que problemas são difíceis de resolver com espaço limitado. Formalmente, um problema de decisão é P-completo (completo para a classe P de complexidade) se ele está em P e se qualquer problema em P é redutível a ele usando uma função de redução adequada. O tipo específico de redução usado varia e pode afetar o conjunto exato de problemas. Se usarmos reduções NC, isto é, reduções que podem operar em tempo polilogarítmico em um computador paralelo com um número polinomial de processadores, então todos os problemas P-completos estão fora da classe NC e, portanto, não podem ser paralelizados eficientemente, sob a suposição não comprovada de que NC ≠ P. Se nós usarmos a mais fraca, isto continua verdadeiro, mas adicionalmente vemos que todos os problemas P-completos estão fora da classe L (também conhecida como classe LSPACE) sob a suposição mais fraca não comprovada de que L ≠ P. Neste último caso, o conjunto P-completo pode ser menor. (pt)
- 在計算複雜度理論內，標示了P-完全的決定型問題對於分析 1.
* 哪些問題很難有效的平行處理， 2.
* 哪些問題很難在有限空間內解決掉。 相當的有用。 更正式的說，一個決定型問題是P-完全(一個P裡面的完全問題)：若這問題本身在P裡面，且所有在P內的問題，都可以化約為此問題。 特定的化約方式會產生使用差異而且會影響問題集合的大小。 若我們使用NC的化約，亦即，可以在內，以平行運作的電腦在多項式個數之內的處理器下完成的化約，基於一個未被證明的假設 NC ≠ P，則我們可知所有的P-完全問題在NC之外，因此無法被有效率的平行處理化。如果我們使用比較弱的 ，前面的說法維持為真，但是多了一個P-完全問題會在L之外的推論， 基於另一個較弱的，尚未被證明的假設L ≠ P。這裡需要注意到根據後者定義出的P-完全 會是一個比前者小一點的集合。 (zh)
|
![[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)