P-complete problems seem to have no parallel algorithm which runsin polylogarithmic time using a polynomial number of processors. AP-complete problem is in the class EP (Efficient and Polynomiallyfast) if and only if there exists a cost optimal algorithm to solveit in T(n)=O(t(n)~ε)(ε<1)ε using P(n) processors such that T(n) xP(n)=O(t(n)), where t(n) is the time complexity of the fastestsequential algorithm which solves the problem.
展开▼
