The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
P-les problèmes complets ne semblent pas avoir d'algorithme parallèle qui s'exécute en temps polylogarithmique en utilisant un nombre polynomial de processeurs. UN P-le problème complet est dans la classe EP (Efficace et polynomialement rapide) si et seulement s'il existe un algorithme optimal en termes de coût pour le résoudre en T(n) = O(t(n)ε) (ε < 1) en utilisant P(n) processeurs tels que T(n)
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Carla Denise CASTANHO, Wei CHEN, Koichi WADA, Akihiro FUJIWARA, "Polynomially Fast Parallel Algorithms for Some P-Complete Problems" in IEICE TRANSACTIONS on Fundamentals,
vol. E84-A, no. 5, pp. 1244-1255, May 2001, doi: .
Abstract: P-complete problems seem to have no parallel algorithm which runs in polylogarithmic time using a polynomial number of processors. A P-complete problem is in the class EP (Efficient and Polynomially fast) if and only if there exists a cost optimal algorithm to solve it in T(n) = O(t(n)ε) (ε < 1) using P(n) processors such that T(n)
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e84-a_5_1244/_p
Copier
@ARTICLE{e84-a_5_1244,
author={Carla Denise CASTANHO, Wei CHEN, Koichi WADA, Akihiro FUJIWARA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Polynomially Fast Parallel Algorithms for Some P-Complete Problems},
year={2001},
volume={E84-A},
number={5},
pages={1244-1255},
abstract={P-complete problems seem to have no parallel algorithm which runs in polylogarithmic time using a polynomial number of processors. A P-complete problem is in the class EP (Efficient and Polynomially fast) if and only if there exists a cost optimal algorithm to solve it in T(n) = O(t(n)ε) (ε < 1) using P(n) processors such that T(n)
keywords={},
doi={},
ISSN={},
month={May},}
Copier
TY - JOUR
TI - Polynomially Fast Parallel Algorithms for Some P-Complete Problems
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1244
EP - 1255
AU - Carla Denise CASTANHO
AU - Wei CHEN
AU - Koichi WADA
AU - Akihiro FUJIWARA
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E84-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2001
AB - P-complete problems seem to have no parallel algorithm which runs in polylogarithmic time using a polynomial number of processors. A P-complete problem is in the class EP (Efficient and Polynomially fast) if and only if there exists a cost optimal algorithm to solve it in T(n) = O(t(n)ε) (ε < 1) using P(n) processors such that T(n)
ER -