viii J;;;l Contents
11.4.6 Construction of the Turing Machine for Computing
the Projection Vi"
336
11.4.7 Construction of the Turing Machine That Can
Perform Composition
338
11.4.8 Construction of the Turing Machine That Can
Perform Recursion
339
11.4.9 Construction of the Turing Machine That Can Perform
Minimization
340
11.5 Supplementary Examples
340
Self-Test
342
Exercises
343
12. COMPLEXITY
12.1 Growth Rate of Functions
346
12.2 The Classes P and NP
349
12.3 Polynomial Time Reduction and NP-completeness
12.4 Importance of NP-complete Problems
352
12.5 SAT is NP-complete
353
12.5.1 Boolean Expressions
353
12.5.2 Coding a Boolean Expression
353
12.5.3 Cook's Theorem
354
12.6 Other NP-complete Problems
359
12.7 Use of NP-completeness
360
12.8 Quantum Computation
360
12.8.1 Quantum Computers
361
12.8.2 Church-Turing Thesis
362
12.8.3 Power of Quantum Computation
363
12.8.4 Conclusion
364
12.9 Supplementary Examples
365
Self-Test
369
Exercises
370
Answers to Self-Tests
Solutions (or Hints) to Chapter-end Exercises
Further Reading
Index
346-371
351
373-374
375-415
417-418
419-422
http://engineeringbooks.net