Cluster Computing and the Power of Edge Recognition
| dc.creator | Hemaspaandra, Lane A. | |
| dc.creator | Homan, Christopher M. | |
| dc.creator | Kosub, Sven | |
| dc.date | 2005-09-19 | |
| dc.date.accessioned | 2026-07-07T06:18:18Z | |
| dc.date.available | 2026-07-07T06:18:18Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/cs/0509060 | |
| dc.identifier | http://arxiv.org/abs/cs/0509060 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/94691 | |
| dc.subject | Computational Complexity | |
| dc.subject | Discrete Mathematics | |
| dc.subject | F.1.3; F.1.1; F.1.2; G.2.1 | |
| dc.title | Cluster Computing and the Power of Edge Recognition | |
| dc.type | text |