The complexity of boolean functions

✍ Scribed by Wegener I.

• Publisher: Wiley
• Year: 1991
• Tongue: English
• Leaves: 470
• Series: Wiley Teubner on Applicable Theory in Computer Science
• Category: Library

✦ Synopsis

Presents a large number of recent research results previously unavailable in book form. Initially deals with the wee-known computation models, and goes on to special types of circuits, parallel computers, and branching programs. Includes basic theory as well recent research findings. Each chapter includes exercises.

✦ Table of Contents

Preface......Page 6
Contents......Page 8
1 INTRODUCTION TO THE THEORY OF BOOLEAN FUNCTIONS AND CIRCUITS......Page 13
2 THE MINIMIZATION OF BOOLEAN FUNCTIONS......Page 34
3 THE DESIGN OF EFFICIENT CIRCUITS FOR SOME FUNDAMENTAL FUNCTIONS......Page 51
4 ASYMPTOTIC RESULTS AND UNIVERSAL CIRCUITS......Page 99
5 LOWER BOUNDS ON CIRCUIT COMPLEXITY......Page 131
6 MONOTONE CIRCUITS......Page 157
7 RELATIONS BETWEEN CIRCUIT SIZE, FORMULA SIZE AND DEPTH......Page 230
8 FORMULA SIZE......Page 247
9 CIRCUITS AND OTHER NON UNIFORM COMPUTATION MODELS VS. TURING MACHINES AND OTHER UNIFORM COMPUTATION MODELS......Page 279
10 HIERARCHIES, MASS PRODUCTION AND REDUCTIONS......Page 308
11 BOUNDED - DEPTH CIRCUITS......Page 332
12 SYNCHRONOUS, PLANAR AND PROBABILISTIC CIRCUITS......Page 352
13 PRAMs AND WRAMs: PARALLEL RANDOM ACCESS MACHINES......Page 373
14 BRANCHING PROGRAMS......Page 426
References......Page 454
Index......Page 468