By Greenlaw R., Hoover H.J., Ruzzo W.
This ebook offers a complete research of an important subject matters in parallel computation. it truly is written in order that it can be used as a self-study advisor to the sector, and researchers in parallel computing will locate it an invaluable reference for a few years to come back. the 1st 1/2 the publication includes an creation to many basic matters in parallel computing. the second one part presents lists of P-complete- and open difficulties. those lists can have lasting worth to researchers in either and academia. The lists of difficulties, with their corresponding comments, the thorough index, and the loads of references upload to the outstanding worth of this source. whereas the intriguing box of parallel computation maintains to extend speedily, this e-book serves as a advisor to investigate performed via 1994 and likewise describes the elemental ideas that new employees might want to comprehend in coming years. it truly is meant for somebody drawn to parallel computing, together with senior point undergraduate scholars, graduate scholars, college, and folks in undefined. As a vital reference, the booklet could be wanted in all educational libraries.
Read or Download Limits to parallel computation. P-completeness theory PDF
Similar theory books
Limits to parallel computation. P-completeness theory
This booklet offers a complete research of an important themes in parallel computation. it's written in order that it can be used as a self-study consultant to the sector, and researchers in parallel computing will locate it an invaluable reference for a few years to come back. the 1st 1/2 the e-book contains an creation to many basic matters in parallel computing.
Advanced Theory of Signal Detection: Weak Signal Detection in Generalized Observations
This ebook encompasses a variety of difficulties of sign detection idea. A generalized commentary version for sign detection difficulties is incorporated. The version comprises a number of attention-grabbing and customary targeted circumstances resembling these describing additive noise, multiplicative noise, and signal-dependent noise. The version may also describe composite indications as well as the standard recognized (deterministic) indications and random (stochastic) signs.
Foreign Federation for info ProcessingThe IFIP sequence publishes cutting-edge ends up in the sciences and applied sciences of data and communique. The scope of the sequence contains: foundations of desktop technology; software program conception and perform; schooling; computing device functions in expertise; conversation platforms; platforms modeling and optimization; info structures; pcs and society; desktops know-how; protection and defense in details processing structures; man made intelligence; and human-computer interplay.
Additional resources for Limits to parallel computation. P-completeness theory
Sample text
When the logical function associated with a gate is not symmetric, the order of the incoming edges into the gate is important. 1 for example, where there is an ⇒ gate. Orientation can be ignored in the usual case in which only symmetric functions like and and or are computed by the gates. 3. THE BOOLEAN CIRCUIT MODEL 29 The resource measures of interest for a circuit are its size and depth. 3 The size of α, denoted size(α), is the number of vertices in α. The depth of α, denoted depth(α), is the length of the longest path in α from an input to an output.
Thus, hereafter the unqualified term uniform will mean logarithmic space uniform. 4 Circuits and PRAMs We have alluded to the fact that many parallel models are equivalent when we consider feasible highly parallel algorithms. That is, if a problem has a feasible highly parallel solution on one model, then it also has one on any equivalent model. Originally the notion of feasible and highly parallel came from the observations that certain problems had polylogarithmic time and polynomial processor solutions on many different models.
The first is how problems are encoded over the binary alphabet; the second is how to view decision and function problems as languages. First, we address the coding issue. Decision and function problems are normally phrased over an alphabet having many more than two symbols. For example, it is often convenient to use delimiters such as #, (, ), and the digits 0 − 9 when expressing a problem. When passing from our usual informal description of a problem to a language recognition question, we would like to preserve the amount of information contained in our original description.
