Boolean Functions and Computation Models

Cover......Page 1
Title Page......Page 4
Copyright Page......Page 5
Dedication......Page 6
Preface......Page 8
Outline of the book......Page 9
How to use the book......Page 10
Acknowledgments......Page 11
Contents......Page 12
1.1 Introduction......Page 16
1.2 Boolean Functions and Formulas......Page 17
1.3 Circuit Model......Page 22
1.4 Basic Functions and Reductions......Page 23
1.5 Nomenclature......Page 26
1.6 Parsing Regular and Context-Free Languages......Page 27
1.7.1 Circuits for Addition and Multiplication......Page 32
1.7.2 Division Using Newton Iteration......Page 36
1.7.3 Division Using Iterated Product......Page 39
1.8.1 Elementary Methods......Page 45
1.8.2 Shannon\'s Method......Page 46
1.8.3 Lupanov\'s Method......Page 47
1.8.4 Symmetric Functions......Page 49
1.9 Reducing the Fan-out......Page 50
1.10 Relating Formula Size and Depth......Page 54
1.11.3 Energy Consumption......Page 60
1.11.4 Boolean Cellular Automata......Page 61
1.11.5 Branching Programs......Page 63
1.11.6 Hopfield Nets......Page 68
1.11.8 Anonymous Networks......Page 69
1.12 Historical and Bibliographical Remarks......Page 70
1.13 Exercises......Page 71
2.1 Introduction......Page 76
2.2 Shannon\'s Lower Bound......Page 78
2.3 Nechiporuk\'s Bound......Page 80
2.4.1 Broken Mosquito Screen......Page 83
2.4.2 Monotonic Real Circuits Are Powerful......Page 92
2.4.3 st-Connectivity......Page 93
2.5 Parity and the Random Restriction Method......Page 105
2.6 Probabilistic Methods......Page 110
2.6.1 Hastad\'s Lower Bound for Parity......Page 111
2.6.2 Depth-k Versus Depth-(k - 1)......Page 114
2.6.3 Razborov\'s Simplification and Decision `Fees......Page 117
2.6.4 A Hybrid Switching Lemma and st-Connectivity......Page 122
2.6.5 Hybrid Switching with the Uniform Distribution......Page 125
2.7.1 Razborov\'s Lower Bound for Majority over Boolean Circuits with Parity......Page 139
2.7.2 Smolensky\'s Lower Bound for MODE Versus MODq......Page 144
2.8.1 On the Strength of MOD,,,, Gates......Page 147
2.8.2 The MoD,,,,-Degree of Threshold Functions......Page 150
2.9 Method of Filters......Page 152
2.10 Eliminating Majority Gates......Page 155
2.11 Circuits for Symmetric Functions......Page 156
2.11.1 Negative Results......Page 158
2.11.2 Positive Results......Page 160
2.12 Probabilistic Circuits......Page 161
2.13 Historical and Bibliographical Remarks......Page 163
2.14 Exercises......Page 165
3.1 Introduction......Page 170
3.2 Definitions and Elementary Properties......Page 171
3.3 P61ya\'s Enumeration Theory......Page 177
3.4 Representability of Permutation Groups......Page 179
3.5 Algorithm for Representing Cyclic Groups......Page 183
3.6 Asymptotics for Invariance Groups......Page 187
3.7 Almost Symmetric Languages......Page 189
3.8 Symmetry and Complexity......Page 193
3.9 Applications to Anonymous Networks......Page 199
3.9.2 Hypercubes......Page 200
3.11 Exercises......Page 209
4.1 Introduction......Page 222
4.2 Threshold for 2-SAT......Page 224
4.3 Unsatisfiability Threshold for 3-SAT......Page 227
4.3.1 A General Method and Local Maxima......Page 228
4.3.2 Method of Single Flips......Page 229
4.3.4 Method of Double Flips......Page 232
4.3.5 Probability Calculations......Page 233
4.4.1 Satisfiability Heuristics......Page 239
4.4.2 Threshold......Page 241
4.5 (2 + p)-SAT......Page 244
4.5.1 Unsatisfiability Threshold......Page 245
4.5.2 Transition from 2-SAT to 3-SAT......Page 247
4.6 Constraint Programming......Page 250
4.6.1 Models of CSP......Page 251
4.6.2 A New Model for Random CSP......Page 253
4.6.3 The Method of Local Maxima......Page 254
4.6.4 Threshold for Model E......Page 256
4.7 Historical and Bibliographical Remarks......Page 257
4.8 Exercises......Page 258
5.1 Introduction......Page 262
5.2 Complexity of Proofs......Page 264
5.3 Gentzen Sequent Calculus LK......Page 270
5.3.1 Completeness......Page 272
5.3.2 Lower Bound for Cut-Free Gentzen......Page 274
5.3.3 Monotonic Sequent Calculus......Page 282
5.4 Resolution......Page 283
5.4.1 Resolution and the PHP......Page 286
5.4.2 Resolution and Odd-Charged Graphs......Page 294
5.4.3 Schoning\'s Expander Graphs and Resolution......Page 300
5.4.4 Width-Bounded Resolution Proofs......Page 306
5.4.5 Interpolation and st-Connectivity......Page 311
5.4.6 Phase Transition and Length of Resolution Proofs......Page 315
5.5 Algebraic Refutation Systems......Page 321
5.5.1 Nullstellensatz......Page 323
5.5.2 Polynomial Calculus......Page 331
5.5.3 Gaussian Calculus......Page 339
5.5.4 Binomial Calculus......Page 341
5.5.5 Lower Bounds for the Polynomial Calculus......Page 347
5.5.6 Random CNF Formulas and the Polynomial Calculus......Page 352
5.6 Cutting Planes CP......Page 358
5.6.1 Completeness of CP......Page 360
5.6.2 Cutting Planes and the PHP......Page 363
5.6.3 Polynomial Equivalence of CP2 and cp......Page 368
5.6.4 Normal Form for CP Proofs......Page 370
5.6.5 Lower Bounds for CP......Page 374
5.6.6 Threshold Logic PTK......Page 381
5.7 Frege Systems......Page 385
5.7.1 Bounded Depth Frege Systems......Page 387
5.7.2 Extended Frege Systems......Page 408
5.7.3 Frege Systems and the PHP......Page 413
5.8 Open Problems......Page 418
5.9 Historical and Bibliographical Remarks......Page 420
5.10 Exercises......Page 421
6.1 Introduction......Page 428
6.2.1 Turing Machines......Page 430
6.2.2 Parallel Machine Model......Page 439
6.2.3 Example Parallel Algorithms......Page 442
6.2.4 LogP Model......Page 448
6.2.5 Circuit Families......Page 449
6.3 Some Recursion Schemes......Page 452
6.3.1 An Algebra for the Logtime Hierarchy LH......Page 453
6.3.2 Bounded Recursion on Notation......Page 465
6.3.3 Bounded Recursion......Page 473
6.3.4 Bounded Minimization......Page 480
6.3.5 Miscellaneous......Page 485
6.3.6 Safe Recursion......Page 493
6.4 A Glimpse of Other Work......Page 502
6.5 Historical and Bibliographical Remarks......Page 503
6.6 Exercises......Page 504
7.2 Type 2 Functionals......Page 512
7.3 Some Closure Properties of Ao......Page 517
7.4 Square-Root and Multiple Recursion......Page 526
7.5 Parallel Machine Model......Page 542
7.6 A-Calculi for Parallel Computable Higher Type Functionals......Page 569
7.6.1 Introduction to Higher Types......Page 570
7.6.2 p-Types......Page 571
7.6.3 Finite Typed Lambda Calculus......Page 573
7.7 Historical and Bibliographical Remarks......Page 579
7.8 Exercises......Page 580
References......Page 584
Index......Page 606