| Information | |
|---|---|
| has gloss | eng: In complexity theory, the notion of P-complete decision problems is useful in the analysis of both: |
| lexicalization | eng: P complete |
| lexicalization | eng: P-complete |
| instance of | e/Complexity class |
| Meaning | |
|---|---|
| Korean | |
| has gloss | kor: 계산 복잡도 이론에서 복잡도 종류 P-완전은 판정 문제의 집합으로, 병렬 컴퓨터가 빠르게 풀 수 있는 문제들을 분석하는 데 쓸모가 있다. 어떤 판정 문제가 P-완전이려면 P에 대해 완전해야 한다. 이는 P에 들어 있는 모든 문제가 프로세스 다항 개가 있는 병렬 컴퓨터로 다항로그 시간을 써서 이 문제로 환산될 수 있다는 뜻이다. 다시 말해서, 어떤 문제 A가 P-완전이려면 P 문제 B마다 B가 A로 병렬 프로세서O(nk)개 써서 O((log n)c) 시간에 환산될 수 있는 상수 c와 k가 있다는 뜻이다. 병렬 프로세서의 정의는 NC를 참고하라. |
| lexicalization | kor: P-완전 |
| Castilian | |
| has gloss | spa: 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. |
| lexicalization | spa: P completo |
| lexicalization | spa: P-completo |
Lexvo © 2008-2025 Gerard de Melo. Contact Legal Information / Imprint