Computer Science – Computational Complexity
Scientific paper
2005-09-19
Computer Science
Computational Complexity
Scientific paper
We study the robustness--the invariance under definition changes--of the cluster class CL#P [HHKW05]. This class contains each #P function that is computed by a balanced Turing machine whose accepting paths always form a cluster with respect to some length-respecting total order with efficient adjacency checks. The definition of CL#P is heavily influenced by the defining paper's focus on (global) orders. In contrast, we define a cluster class, CLU#P, to capture what seems to us a more natural model of cluster computing. We prove that the naturalness is costless: CL#P = CLU#P. Then we exploit the more natural, flexible features of CLU#P to prove new robustness results for CL#P and to expand what is known about the closure properties of CL#P. The complexity of recognizing edges--of an ordered collection of computation paths or of a cluster of accepting computation paths--is central to this study. Most particularly, our proofs exploit the power of unique discovery of edges--the ability of nondeterministic functions to, in certain settings, discover on exactly one (in some cases, on at most one) computation path a critical piece of information regarding edges of orderings or clusters.
Hemaspaandra Lane A.
Homan Christopher M.
Kosub Sven
No associations
LandOfFree
Cluster Computing and the Power of Edge Recognition does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Cluster Computing and the Power of Edge Recognition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cluster Computing and the Power of Edge Recognition will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-1371