Algorithmic complexity and communication problems

Cover......Page 1
Half Title......Page 2
Title Page......Page 4
Copyright Page......Page 5
Table of Contents......Page 6
Notation......Page 10
Graphs: notation and definitions......Page 14
Introduction......Page 16
  1.1: Satisfiability......Page 22
  1.3: The matching problem......Page 24
  1.4: Knapsack......Page 25
  1.6: Noisy channel: coding and decoding......Page 26
  2.1: Decision problems......Page 27
  2.2: Universes......Page 28
  2.3: Languages, relations and encoding schemes......Page 29
  2.4: Reasonable encoding schemes......Page 30
  2.5: Intuitive lengths......Page 32
  3.1: Language transformations and reductions......Page 33
  3.2: Completeness......Page 35
  3.3: An example of transformation: from SAT to 3-SAT......Page 36
  4.1: Efficiency of algorithms and programs......Page 38
  4.3: Hardness of problems......Page 40
  4.4: How to classify a problem?......Page 41
Chapter II: Machines, languages and problems. Classes P and NP......Page 44
  1.1: Formal approach......Page 45
  1.2: Intuitive approach......Page 47
  1.3: Computations......Page 48
  1.4: Machine composition......Page 50
  2.2: Computation time and complexity......Page 51
  3.1: Decision machines......Page 53
  3.2: Recursive and polynomial reductions......Page 55
 4: Polynomial problems......Page 56
  5.1: Short certificate, recursive and polynomial relations......Page 58
  5.3: Nondeterministic decision and NP languages......Page 60
  5.4: Completeness of NP, the classes NP and co-NP......Page 63
  5.5: Nondeterministic Polynomial problems......Page 65
  6.2: The problems SAT and 3-SAT......Page 67
  6.3: Three–dimensional matching......Page 72
  6.4: The k-colouring problem......Page 76
  6.5: Exercises......Page 80
 7: Survival principles......Page 83
  8.1: Partition and knapsack......Page 84
  8.2: The partition problem (continued)......Page 87
  8.3: The partition problem (end)......Page 88
  8.4: Pseudo-polynomial algorithms and problems......Page 89
  8.5: Strongly NP-complete problems......Page 90
 9: Exercises and problems......Page 91
Chapter III: NP-hard problems and languages and complements to algorithmic complexity......Page 100
  1.1: Search and optimization problems: an intuitive approach......Page 101
  1.2: Search problems: formal approach......Page 102
  1.3: Oracle computing machines: intuitive approach......Page 103
  1.4: Oracle machines: formal approach......Page 104
  1.5: Turing reductions......Page 106
  1.6: NP-hard problems......Page 107
  2.1: Result: the structure of NP......Page 109
  2.2: Nondeterministic oracle decision and polynomial hierarchy......Page 111
  2.3: Polynomial quantifications and characterizations......Page 114
  2.4: Complete problems......Page 116
  2.5: Collapse?......Page 119
  3.1: Space complexity and space reductions......Page 120
  3.3: Enumeration problems......Page 123
  3.4: Probabilistic methods......Page 124
  3.5: Relativization......Page 125
 1: Linear codes......Page 128
 2: Dual code, syndrome, error detection......Page 130
  3.1: Complexity of decoding......Page 133
  3.2: Standard array......Page 138
  3.3: Syndrome decoding......Page 139
 4: A few examples: perfect codes......Page 142
  5.1: Variations on minimal weight (MINW)......Page 147
  5.2: Complexity of two related problems......Page 149
  5.3: Some specific instances......Page 153
 6: The covering radius......Page 155
 7: An application to writing on memories......Page 157
 A.1: The problem of linear decoding with preprocessing......Page 162
 A.2: П2-completeness of UB-CR......Page 164
  1: Introduction......Page 168
  2: Generator polynomial......Page 169
  3: Systematic coding......Page 170
  4: Comments on the decoding of cyclic codes......Page 171
  5: Primitive n-th roots of unity......Page 172
  6: Binary primitive BCH codes......Page 176
  7: Algebraic decoding of binary BCH codes......Page 179
 A.4: NP-completeness of some problems related to MINW......Page 180
 1: General introduction to cryptology......Page 190
  2.1: One-way functions......Page 194
  2.3: Public-key signature......Page 197
  2.4: Combined enciphering and signature......Page 198
  3.1: Prime numbers, factorization......Page 200
  3.2: The RSA......Page 203
  3.3: Choosing parameters......Page 207
  4.1: An NP-complete problem: the knapsack......Page 209
  4.2: Order relations and knapsacks. Two examples......Page 211
  4.3: Cryptographic use of the knapsack......Page 216
  4.4: Remarks on the preprocessing of knapsacks......Page 219
  4.5: Cryptanalysis of the knapsack......Page 223
  5.1: An NP-complete problem: linear decoding......Page 229
  5.2: A brief introduction to Goppa codes......Page 230
  5.3: Enciphering with McEliece\'s system......Page 231
  5.4: Choosing parameters and analysis of the security......Page 233
 6: Authentication protocols......Page 237
  6.1: Zero-knowledge interactive proofs......Page 240
  6.2: Zero-knowledge authentication: Fiat-Shamir\'s scheme......Page 243
  6.3: Authentication and error-correcting codes......Page 245
Appendix to Chapter V: Permutation decoding......Page 246
 1: Introduction to information theory......Page 248
 3: Rate-distortion theory......Page 251
  4.2: Average criterion......Page 253
 5: On complexity......Page 256
Chain of polynomial reductions which are used......Page 260
Bibliography......Page 262
Index......Page 272