Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1016.94046
Clote, Peter; Kranakis, Evangelos
Boolean functions and computation models. (English)
[B] Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. xiv, 601 p. EUR 41.95 (net); sFr 72.00; \sterling 29.50; \$ 44.95 (2002). ISBN 3-540-59436-1

The authors give a survey of the present research concerning the study of Boolean functions, formulas, circuits and propositional proof systems. The first three chapters are dedicated to Boolean functions and circuit lower and upper bounds. Chapter 4 deals with the threshold phenomenon for 3-SAT (conjunctive normal forms on $n$ variables and 3 literals per clause). In Chapter 5 several propositional proof systems are studied which have relevance to complexity theory: Gentzen calculus, resolution, algebraic refutation systems, Frege systems. Various computational models (uniform circuit families, Turing machines, parallel random access machines) are given in Chapter 6 and some features of parallel computation are illustrated by giving example programs. The last chapter includes an interesting study of the higher type functional complexity theory. Several open problems are presented.
[Nicolae Tăndăreanu (Craiova)]

MSC 2000:: *94C10 Switching theory
68Q10 Modes of computation
68Q17 Computational difficulty of problems
94C05 Analytic circuit theory
03D15 Complexity of computation

Keywords: Boolean function; circuit; proof system; Turing machine; parallel machine model

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]