Models of Computation

by Savage, John E.

• ISBN13: 9780201895391
• ISBN10: 0201895390
• Format: Paperback
• Copyright: 1997-10-01
• Publisher: Addison-Wesley

Summary

The focus of this book is on finite problems and concrete computational models. It covers the traditional topics of formal languages, automata and complexity classes, as well as an introduction to the more modern topics of space-time tradeoffs, memory hierarchies, parallel computation, the VLSI model, and circuit complexity. These topics are integrated throughout the book as illustrated by the early introduction of P-complete and NP-complete problems. Models of Computation provides the first textbook treatment of space-time tradeoffs and memory hierarchies. It gives a comprehensive introduction to computational complexity as well as a brief but modern coverage of circuit complexity. Parallelism is integrated throughout the book.

Table of Contents

Preface	vii
I Overview of the Book	1	(32)
1 The Role of Theory in Computer Science	3	(30)
1.1 A Brief History of Theoretical Computer Science	4	(3)
1.1.1 Early Years	4	(1)
1.1.2 1950s	5	(1)
1.1.3 1960s	5	(1)
1.1.4 1970s	5	(1)
1.1.5 1980s and 1990s	6	(1)
1.2 Mathematical Preliminaries	7	(7)
1.2.1 Sets	7	(1)
1.2.2 Number Systems	8	(1)
1.2.3 Languages and Strings	9	(1)
1.2.4 Relations	9	(1)
1.2.5 Graphs	10	(1)
1.2.6 Matrices	11	(1)
1.2.7 Functions	11	(2)
1.2.8 Rate of Growth of Functions	13	(1)
1.3 Methods of Proof	14	(2)
1.4 Computational Models	16	(7)
1.4.1 Logic Circuits	16	(2)
1.4.2 Finite-State Machines	18	(1)
1.4.3 Random-Access Machine	19	(1)
1.4.4 Other Models	20	(1)
1.4.5 Formal Languages	21	(2)
1.5 Computational Complexity	23	(4)
1.5.1 A Computational Inequality	23	(1)
1.5.2 Tradeoffs in Space, Time, and I O Operations	24	(2)
1.5.3 Complexity Classes	26	(1)
1.5.4 Circuit Complexity	27	(1)
1.6 Parallel Computation	27	(2)
Problems	29	(3)
Chapter Notes	32	(1)
II General Computational Models	33	(292)
2 Logic Circuits	35	(56)
2.1 Designing Circuits	36	(1)
2.2 Straight-Line Programs and Circuits	36	(6)
2.2.1 Functions Computed by Circuits	38	(1)
2.2.2 Circuits That Compute Functions	39	(1)
2.2.3 Circuit Complexity Measures	40	(1)
2.2.4 Algebraic Properties of Boolean Functions	40	(2)
2.3 Normal-Form Expansions of Boolean Functions	42	(4)
2.3.1 Disjunctive Normal Form	42	(1)
2.3.2 Conjunctive Normal Form	43	(1)
2.3.3 SOPE and POSE Normal Forms	44	(1)
2.3.4 Ring-Sum Expansion	45	(1)
2.3.5 Comparison of Normal Forms	45	(1)
2.4 Reductions Between Functions	46	(1)
2.5 Specialized Circuits	47	(8)
2.5.1 Logical Operations	48	(1)
2.5.2 Shifting Functions	48	(3)
2.5.3 Encoder	51	(2)
2.5.4 Decoder	53	(1)
2.5.5 Multiplexer	54	(1)
2.5.6 Demultiplexer	55	(1)
2.6 Prefix Computations	55	(3)
2.6.1 An Efficient Parallel Prefix Circuit	57	(1)
2.7 Addition	58	(3)
2.7.1 Carry-Lookahead Addition	60	(1)
2.8 Subtraction	61	(1)
2.9 Multiplication	62	(6)
2.9.1 Carry-Save Multiplication	64	(2)
2.9.2 Divide-and-Conquer Multiplication	66	(1)
2.9.3 Fast Multiplication	67	(1)
2.9.4 Very Fast Multiplication	67	(1)
2.9.5 Reductions to Multiplication	68	(1)
2.10 Reciprocal and Division	68	(6)
2.10.1 Reductions to the Reciprocal	72	(2)
2.11 Symmetric Functions	74	(3)
2.12 Most Boolean Functions Are Complex	77	(2)
2.13 Upper Bounds on Circuit Size	79	(3)
Problems	82	(6)
Chapter Notes	88	(3)
3 Machines with Memory	91	(62)
3.1 Finite-State Machines	92	(8)
3.1.1 Functions Computed by FSMs	94	(1)
3.1.2 Computational Inequalities for the FSM	95	(1)
3.1.3 Circuits Are Universal for Bounded FSM Computations	96	(1)
3.1.4 Interconnections of Finite-State Machines	97	(1)
3.1.5 Nondeterministic Finite-State Machines	98	(2)
3.2 Simulating FSMs with Shallow Circuits(*)	100	(6)
3.2.1 A Shallow Circuit Simulating Addition	105	(1)
3.3 Designing Sequential Circuits	106	(4)
3.3.1 Binary Memory Devices	109	(1)
3.4 Random-Access Machines	110	(5)
3.4.1 The RAM Architecture	110	(1)
3.4.2 The RAM as FSM	111	(1)
3.4.3 RAM Programs	112	(2)
3.4.4 Universality of the RAM	114	(1)
3.5 Random-Access Memory Design	115	(2)
3.6 Computational Inequalities for the RAM	117	(1)
3.7 Turing Machines	118	(3)
3.7.1 Nondeterministic Turing Machines	120	(1)
3.8 Universality of the Turing Machine	121	(3)
3.9 Turing Machine Circuit Simulations	124	(13)
3.9.1 A Simple Circuit Simulation of TM Computations	124	(3)
3.9.2 Computational Inequalities for Turing Machines	127	(1)
3.9.3 Reductions from Turing to Circuit Computations	128	(2)
3.9.4 Definitions of P-Complete and NP-Complete Languages	130	(1)
3.9.5 Reductions to P-Complete Languages	130	(2)
3.9.6 Reductions to NP-Complete Languages	132	(2)
3.9.7 An Efficient Circuit Simulation of TM Computations(*)	134	(3)
3.10 Design of a Simple CPU	137	(10)
3.10.1 The Register Set	138	(1)
3.10.2 The Fetch-and-Execute Cycle	139	(1)
3.10.3 The Instruction Set	139	(1)
3.10.4 Assembly-Language Programming	140	(2)
3.10.5 Timing and Control	142	(4)
3.10.6 CPU Circuit Size and Depth	146	(1)
3.10.7 Emulation	147	(1)
Problems	147	(5)
Chapter Notes	152	(1)
4 Finite-State Machines and Pushdown Automata	153	(56)
4.1 Finite-State Machine Models	154	(2)
4.2 Equivalence of DFSMs and NFSMs	156	(2)
4.3 Regular Expressions	158	(2)
4.4 Regular Expressions and FSMs	160	(8)
4.4.1 Recognition of Regular Expressions by FSMs	160	(4)
4.4.2 Regular Expressions Describing FSM Languages	164	(4)
4.4.3 grep--Searching for Strings in Files	168	(1)
4.5 The Pumping Lemma for FSMs	168	(2)
4.6 Properties of Regular Languages	170	(1)
4.7 State Minimization(*)	171	(6)
4.7.1 Equivalence Relations on Languages and States	171	(3)
4.7.2 The Myhill-Nerode Theorem	174	(1)
4.7.3 A State Minimization Algorithm	175	(2)
4.8 Pushdown Automata	177	(4)
4.9 Formal Languages	181	(3)
4.9.1 Phrase-Structure Languages	182	(1)
4.9.2 Context-Sensitive Languages	183	(1)
4.9.3 Context-Free Languages	183	(1)
4.9.4 Regular Languages	184	(1)
4.10 Regular Language Recognition	184	(2)
4.11 Parsing Context-Free languages	186	(6)
4.12 CFL Acceptance with Pushdown Automata(*)	192	(5)
4.13 Properties of Context-Free Languages	197	(3)
4.13.1 CFL Pumping Lemma	197	(1)
4.13.2 CFL Closure Properties	198	(2)
Problems	200	(7)
Chapter Notes	207	(2)
5 Computability	209	(28)
5.1 The Standard Turing Machine Model	210	(3)
5.1.1 Programming the Turing Machine	211	(2)
5.2 Extensions to the Standard Turing Machine Model	213	(5)
5.2.1 Multi-Tape Turing Machines	213	(1)
5.2.2 Nondeterministic Turing Machines	214	(2)
5.2.3 Oracle Turing Machines	216	(1)
5.2.4 Representing Restricted Models of Computation	217	(1)
5.3 Configuration Graphs	218	(1)
5.4 Phrase-Structure Languages and Turing Machines	219	(1)
5.5 Universal Turing Machines	220	(2)
5.6 Encodings of Strings and Turing Machines	222	(1)
5.7 Limits on Language Acceptance	223	(3)
5.7.1 Decidable Languages	223	(1)
5.7.2 A Language That Is Not Recursively Enumerable	224	(1)
5.7.3 Recursively Enumerable but Not Decidable Languages	225	(1)
5.8 Reducibility and Unsolvability	226	(4)
5.8.1 Reducibility	226	(1)
5.8.2 Unsolvable Problems	227	(3)
5.9 Functions Computed by Turing Machines	230	(3)
5.9.1 Primitive Recursive Functions	231	(1)
5.9.2 Partial Recursive Functions	232	(1)
5.9.3 Partial Recursive Functions are RAM-Computable	233	(1)
Problems	233	(3)
Chapter Notes	236	(1)
6 Algebraic and Combinatorial Circuits	237	(44)
6.1 Straight-Line Programs	238	(1)
6.2 Mathematical Preliminaries	239	(5)
6.2.1 Rings	239	(1)
6.2.2 Matrices	240	(4)
6.3 Matrix Multiplication	244	(4)
6.3.1 Strassen's Algorithm	245	(3)
6.4 Transitive Closure	248	(4)
6.5 Matrix Inversion	252	(10)
6.5.1 Symmetric Positive Definite Matrices	253	(1)
6.5.2 Schur Factorization	254	(1)
6.5.3 Inversion of Triangular Matrices	255	(2)
6.5.4 LDL(T) Factorization of SPD Matrices	257	(3)
6.5.5 Fast Matrix Inversion(*)	260	(2)
6.6 Solving Linear Systems	262	(1)
6.7 Convolution and the FFT Algorithm	263	(7)
6.7.1 Commutative Rings(*)	264	(1)
6.7.2 The Discrete Fourier Transform	264	(2)
6.7.3 Fast Fourier Transform	266	(2)
6.7.4 Convolution Theorem	268	(2)
6.8 Merging and Sorting Networks	270	(4)
6.8.1 Sorting Via Odd-Even Merging	271	(3)
6.8.2 Fast Sorting Networks	274	(1)
Problems	274	(4)
Chapter Notes	278	(3)
7 Parallel Computation	281	(44)
7.1 Parallel Computational Models	282	(1)
7.2 Memoryless Parallel Computers	282	(1)
7.3 Parallel Computers with Memory	283	(6)
7.3.1 Flynn's Taxonomy	285	(1)
7.3.2 The Data-Parallel Model	286	(1)
7.3.3 Networked Computers	287	(2)
7.4 The Performance of Parallel Algorithms	289	(3)
7.4.1 Amdahl's Law	290	(1)
7.4.2 Brent's Principle	291	(1)
7.5 Multidimensional Meshes	292	(6)
7.5.1 Matrix-Vector Multiplication on a Linear Array	293	(1)
7.5.2 Sorting on Linear Arrays	294	(1)
7.5.3 Matrix Multiplication on a 2D Mesh	295	(2)
7.5.4 Embedding of 1D Arrays in 2D Meshes	297	(1)
7.6 Hypercube-Based Machines	298	(3)
7.6.1 Embedding Arrays in Hypercubes	299	(1)
7.6.2 Cube-Connected Cycles	300	(1)
7.7 Normal Algorithms	301	(8)
7.7.1 Summing on the Hypercube	302	(1)
7.7.2 Broadcasting on the Hypercube	303	(1)
7.7.3 Shifting on the Hypercube	303	(1)
7.7.4 Shuffle and Unshuffle Permutations on Linear Arrays	304	(2)
7.7.5 Fully Normal Algorithms on Two-Dimensional Arrays	306	(1)
7.7.6 Normal Algorithms on Cube-Connected Cycles	307	(1)
7.7.7 Fast Matrix Multiplication on the Hypercube	308	(1)
7.8 Routing in Networks	309	(2)
7.8.1 Local Routing Networks	309	(1)
7.8.2 Global Routing Networks	310	(1)
7.9 The PRAM Model	311	(6)
7.9.1 Simulating Trees, Arrays, and Hypercubes on the PRAM	313	(1)
7.9.2 The Power of Concurrency	314	(1)
7.9.3 Simulating the PRAM on a Hypercube Network	315	(2)
7.9.4 Circuits and the CREW PRAM	317	(1)
7.10 The BSP and LogP Models	317	(1)
Problems	318	(4)
Chapter Notes	322	(3)
III Computational Complexity	325	(280)
8 Complexity Classes	327	(64)
8.1 Introduction	328	(1)
8.2 Languages and Problems	328	(2)
8.2.1 Complements of Languages and Decision Problems	329	(1)
8.3 Resource Bounds	330	(1)
8.4 Serial Computational Models	331	(3)
8.4.1 The Random-Access Machine	331	(1)
8.4.2 Turing Machine Models	332	(2)
8.5 Classification of Decision Problems	334	(9)
8.5.1 Space and Time Hierarchies	336	(1)
8.5.2 Time-Bounded Complexity Classes	337	(1)
8.5.3 Space-Bounded Complexity Classes	338	(3)
8.5.4 Relations Between Time- and Space-Bounded Classes	341	(1)
8.5.5 Space-Bounded Functions	342	(1)
8.6 Complements of Complexity Classes	343	(6)
8.6.1 The Complement of NP	347	(2)
8.7 Reductions	349	(1)
8.8 Hard and Complete Problems	350	(2)
8.9 P-Complete Problems	352	(3)
8.10 NP-Complete Problems	355	(8)
8.10.1 NP-Complete Satisfiability Problems	356	(1)
8.10.2 Other NP-Complete Problems	357	(6)
8.11 The Boundary Between P and NP	363	(2)
8.12 PSPACE-Complete Problems	365	(7)
8.12.1 A First PSPACE-Complete Problem	365	(4)
8.12.2 Other PSPACE-Complete Problems	369	(3)
8.13 The Circuit Model of Computation	372	(4)
8.13.1 Uniform Families of Circuits	373	(1)
8.13.2 Uniform Circuits Are Equivalent to Turing Machines	374	(2)
8.14 The Parallel Random-Access Machine Model	376	(4)
8.14.1 Equivalence of the CREW PRAM and Circuits	376	(3)
8.14.2 The Parallel Computation Thesis	379	(1)
8.15 Circuit Complexity Classes	380	(3)
8.15.1 Efficiently Parallelizable Languages	380	(2)
8.15.2 Circuits of Polynomial Size	382	(1)
Problems	383	(5)
Chapter Notes	388	(3)
9 Circuit Complexity	391	(70)
9.1 Circuit Models and Measures	392	(2)
9.1.1 Circuit Models	392	(1)
9.1.2 Complexity Measures	393	(1)
9.2 Relationships Among Complexity Measures	394	(5)
9.2.1 Effect of Fan-Out on Circuit Size	394	(2)
9.2.2 Effect of Basis Change on Circuit Size and Depth	396	(1)
9.2.3 Formula Size Versus Circuit Depth	396	(3)
9.3 Lower-Bound Methods for General Circuits	399	(5)
9.3.1 Simple Lower Bounds	399	(1)
9.3.2 The Gate-Elimination Method for Circuit Size	400	(4)
9.4 Lower-Bound Methods for Formula Size	404	(5)
9.4.1 The Neciporuk Lower Bound	405	(2)
9.4.2 The Krapchenko Lower Bound	407	(2)
9.5 The Power of Negation	409	(3)
9.6 Lower-Bound Methods for Monotone Circuits	412	(24)
9.6.1 The Path-Elimination Method	413	(4)
9.6.2 The Function Replacement Method	417	(7)
9.6.3 The Approximation Method	424	(7)
9.6.4 Slice Functions	431	(5)
9.7 Circuit Depth	436	(14)
9.7.1 Communication Complexity	437	(1)
9.7.2 General Depth and Communication Complexity	438	(2)
9.7.3 Monotone Depth and Communication Complexity	440	(2)
9.7.4 The Monotone Depth of the Clique Function	442	(5)
9.7.5 Bounded-Depth Circuits	447	(3)
Problems	450	(5)
Chapter Notes	455	(6)
10 Space--Time Tradeoffs	461	(68)
10.1 The Pebble Game	462	(2)
10.1.1 The Pebble Game Versus the Branching Program	462	(1)
10.1.2 Playing the Pebble Game	463	(1)
10.2 Space Lower Bounds	464	(2)
10.3 Extreme Tradeoffs	466	(2)
10.4 Grigoriev's Lower-Bound Method	468	(4)
10.4.1 Flow Properties of Functions	468	(2)
10.4.2 The Lower-Bound Method in the Basic Pebble Game	470	(2)
10.4.3 First Matrix Multiplication Bound	472	(1)
10.5 Applications of Grigoriev's Method	472	(10)
10.5.1 Convolution	473	(1)
10.5.2 Cyclic Shifting	474	(1)
10.5.3 Integer Multiplication	475	(1)
10.5.4 Matrix Multiplication	476	(3)
10.5.5 Discrete Fourier Transform	479	(2)
10.5.6 Merging Networks	481	(1)
10.6 Worst-Case Tradeoffs for Pebble Games(*)	482	(1)
10.7 Upper Bounds on Space(*)	483	(1)
10.8 Lower Bound on Space for General Graphs(*)	484	(4)
10.9 Branching Programs	488	(7)
10.9.1 Branching Programs and Other Models	493	(2)
10.10 Straight-Line Versus Branching Programs	495	(2)
10.10.1 Efficient Branching Programs for Cyclic Shift	496	(1)
10.10.2 Efficient Branching Programs for Merging	496	(1)
10.11 The Borodin-Cook Lower-Bound Method	497	(4)
10.12 Properties of "nice" and "ok" Matrices(*)	501	(3)
10.13 Applications of the Borodin-Cook Method	504	(15)
10.13.1 Convolution	505	(1)
10.13.2 Integer Multiplication	506	(1)
10.13.3 Matrix-Vector Product	507	(2)
10.13.4 Matrix Multiplication(*)	509	(2)
10.13.5 Matrix Inversion	511	(2)
10.13.6 Discrete Fourier Transform	513	(1)
10.13.7 Unique Elements	514	(3)
10.13.8 Sorting	517	(2)
Problems	519	(7)
Chapter Notes	526	(3)
11 Memory-Hierarchy Tradeoffs	529	(46)
11.1 The Red-Blue Pebble Game	530	(3)
11.1.1 Playing the Red-Blue Pebble Game	532	(1)
11.1.2 Balanced Computer Systems	532	(1)
11.2 The Memory-Hierarchy Pebble Game	533	(2)
11.2.1 Playing the MHG	535	(1)
11.3 I O-Time Relationships	535	(2)
11.4 The Hong-Kung Lower-Bound Method	537	(2)
11.5 Tradeoffs Between Space and I O Time	539	(16)
11.5.1 Matrix-Vector Product	539	(2)
11.5.2 Matrix-Matrix Multiplication	541	(5)
11.5.3 The Fast Fourier Transform	546	(6)
11.5.4 Convolution	552	(3)
11.6 Block I O in the MHG	555	(3)
11.7 Simulating a Fast Memory in the MHG	558	(1)
11.8 RAM-Based I O Models	559	(4)
11.8.1 The Block-Transfer Model	559	(4)
11.9 The Hierarchical Memory Model	563	(4)
11.9.1 Lower Bounds for the HMM	564	(3)
11.9.2 Upper Bounds for the HMM	567	(1)
11.10 Competitive Memory Management	567	(2)
11.10.1 Two-Level Memory-Management Algorithms	568	(1)
Problems	569	(4)
Chapter Notes	573	(2)
12 VLSI Models of Computation	575	(30)
12.1 The VSLI Challenge	576	(2)
12.1.1 Chip Fabrication	576	(1)
12.1.2 Design and Layout	577	(1)
12.2 VLSI Physical Models	578	(1)
12.3 VLSI Computational Models	579	(1)
12.4 VLSI Performance Criteria	580	(1)
12.5 Chip Layout	581	(5)
12.5.1 The H-Tree Layout	581	(2)
12.5.2 Multi-dimensional Mesh Layouts	583	(1)
12.5.3 Layout of the CCC Network	584	(2)
12.6 Area-Time Tradeoffs	586	(6)
12.6.1 Planar Circuit Size	586	(1)
12.6.2 Computational Inequalities	587	(2)
12.6.3 The Planar Separator Theorem	589	(3)
12.7 The Performance of VLSI Algorithms	592	(5)
12.7.1 The Performance VLSI Algorithms on Functions	593	(2)
12.7.2 The Performance of VLSI Algorithms on Predicates	595	(2)
12.8 Area Bounds	597	(1)
Problems	598	(3)
Chapter Notes	601	(4)
Bibliography	605	(18)
Index	623