The Nature of Computation

Description

Computational complexity is one of the most beautiful fields of modern mathematics, and it is increasingly relevant to other sciences ranging from physics to biology. But this beauty is often buried underneath layers of unnecessary formalism, and exciting recent results like interactive proofs, cryptography, and quantum computing are usually considered too "advanced" to show to the typical student. The aim of this book is to bridge both gaps by explaining the deep ideas of theoretical computer science in a clear and enjoyable fashion, making them accessible to non computer scientists and to computer scientists who finally want to understand what their formalisms are actually telling. This book gives a lucid and playful explanation of the field, starting with P and NP-completeness. The authors explain why the P vs. NP problem is so fundamental, and why it is so hard to resolve. They then lead the reader through the complexity of mazes and games; optimization in theory and practice; randomized algorithms, interactive proofs, and pseudorandomness; Markov chains and phase transitions; and the outer reaches of quantum computing. At every turn, they use a minimum of formalism, providing explanations that are both deep and accessible. The book is intended for graduates and undergraduates, scientists from other areas who have long wanted to understand this subject, and experts who want to fall in love with this field all over again. a0001......Page 1 a0002......Page 2 a0003......Page 3 a0004......Page 4 a0005......Page 5 a0006......Page 6 p0881......Page 0 a0008......Page 8 a0009......Page 9 a0010......Page 10 a0011......Page 11 a0012......Page 12 a0013......Page 13 a0014......Page 14 a0015......Page 15 a0016......Page 16 p0001......Page 17 p0002......Page 18 p0003......Page 19 p0004......Page 20 p0005......Page 21 p0006......Page 22 p0007......Page 23 p0008......Page 24 p0009......Page 25 p0010......Page 26 p0011......Page 27 p0012......Page 28 p0013......Page 29 p0014......Page 30 p0015......Page 31 p0016......Page 32 p0017......Page 33 p0018......Page 34 p0019......Page 35 p0020......Page 36 p0021......Page 37 p0022......Page 38 p0023......Page 39 p0024......Page 40 p0025......Page 41 p0026......Page 42 p0027......Page 43 p0028......Page 44 p0029......Page 45 p0030......Page 46 p0031......Page 47 p0032......Page 48 p0034......Page 50 p0035......Page 51 p0036......Page 52 p0037......Page 53 p0038......Page 54 p0039......Page 55 p0040......Page 56 p0041......Page 57 p0042......Page 58 p0043......Page 59 p0044......Page 60 p0045......Page 61 p0046......Page 62 p0047......Page 63 p0048......Page 64 p0049......Page 65 p0050......Page 66 p0051......Page 67 p0052......Page 68 p0053......Page 69 p0054......Page 70 p0055......Page 71 p0056......Page 72 p0057......Page 73 p0058......Page 74 p0059......Page 75 p0060......Page 76 p0061......Page 77 p0062......Page 78 p0063......Page 79 p0064......Page 80 p0065......Page 81 p0066......Page 82 p0067......Page 83 p0068......Page 84 p0069......Page 85 p0070......Page 86 p0071......Page 87 p0072......Page 88 p0073......Page 89 p0074......Page 90 p0075......Page 91 p0076......Page 92 p0077......Page 93 p0078......Page 94 p0079......Page 95 p0080......Page 96 p0081......Page 97 p0082......Page 98 p0083......Page 99 p0084......Page 100 p0085......Page 101 p0086......Page 102 p0087......Page 103 p0088......Page 104 p0089......Page 105 p0091......Page 107 p0092......Page 108 p0093......Page 109 p0094......Page 110 p0095......Page 111 p0096......Page 112 p0097......Page 113 p0098......Page 114 p0099......Page 115 p0100......Page 116 p0101......Page 117 p0102......Page 118 p0103......Page 119 p0104......Page 120 p0105......Page 121 p0106......Page 122 p0107......Page 123 p0108......Page 124 p0109......Page 125 p0110......Page 126 p0111......Page 127 p0112......Page 128 p0113......Page 129 p0114......Page 130 p0115......Page 131 p0116......Page 132 p0117......Page 133 p0118......Page 134 p0119......Page 135 p0121......Page 137 p0122......Page 138 p0123......Page 139 p0124......Page 140 p0125......Page 141 p0126......Page 142 p0127......Page 143 p0128......Page 144 p0129......Page 145 p0130......Page 146 p0131......Page 147 p0132......Page 148 p0133......Page 149 p0134......Page 150 p0135......Page 151 p0136......Page 152 p0137......Page 153 p0138......Page 154 p0139......Page 155 p0140......Page 156 p0141......Page 157 p0142......Page 158 p0143......Page 159 p0144......Page 160 p0145......Page 161 p0146......Page 162 p0147......Page 163 p0148......Page 164 p0149......Page 165 p0150......Page 166 p0151......Page 167 p0152......Page 168 p0153......Page 169 p0154......Page 170 p0155......Page 171 p0156......Page 172 p0157......Page 173 p0158......Page 174 p0159......Page 175 p0160......Page 176 p0161......Page 177 p0162......Page 178 p0163......Page 179 p0164......Page 180 p0165......Page 181 p0166......Page 182 p0167......Page 183 p0168......Page 184 p0169......Page 185 p0170......Page 186 p0171......Page 187 p0172......Page 188 p0173......Page 189 p0174......Page 190 p0175......Page 191 p0176......Page 192 p0177......Page 193 p0178......Page 194 p0179......Page 195 p0180......Page 196 p0181......Page 197 p0182......Page 198 p0183......Page 199 p0184......Page 200 p0185......Page 201 p0186......Page 202 p0187......Page 203 p0188......Page 204 p0189......Page 205 p0190......Page 206 p0191......Page 207 p0192......Page 208 p0193......Page 209 p0194......Page 210 p0195......Page 211 p0196......Page 212 p0197......Page 213 p0198......Page 214 p0199......Page 215 p0200......Page 216 p0201......Page 217 p0202......Page 218 p0203......Page 219 p0204......Page 220 p0205......Page 221 p0206......Page 222 p0207......Page 223 p0208......Page 224 p0209......Page 225 p0210......Page 226 p0211......Page 227 p0212......Page 228 p0213......Page 229 p0214......Page 230 p0215......Page 231 p0216......Page 232 p0217......Page 233 p0218......Page 234 p0219......Page 235 p0220......Page 236 p0221......Page 237 p0222......Page 238 p0223......Page 239 p0224......Page 240 p0225......Page 241 p0226......Page 242 p0227......Page 243 p0228......Page 244 p0229......Page 245 p0230......Page 246 p0231......Page 247 p0232......Page 248 p0233......Page 249 p0234......Page 250 p0235......Page 251 p0236......Page 252 p0237......Page 253 p0238......Page 254 p0239......Page 255 p0240......Page 256 p0241......Page 257 p0242......Page 258 p0243......Page 259 p0244......Page 260 p0245......Page 261 p0246......Page 262 p0247......Page 263 p0248......Page 264 p0249......Page 265 p0250......Page 266 p0251......Page 267 p0252......Page 268 p0253......Page 269 p0254......Page 270 p0255......Page 271 p0256......Page 272 p0257......Page 273 p0258......Page 274 p0259......Page 275 p0260......Page 276 p0261......Page 277 p0262......Page 278 p0263......Page 279 p0264......Page 280 p0265......Page 281 p0266......Page 282 p0267......Page 283 p0268......Page 284 p0269......Page 285 p0270......Page 286 p0271......Page 287 p0272......Page 288 p0273......Page 289 p0274......Page 290 p0275......Page 291 p0276......Page 292 p0277......Page 293 p0278......Page 294 p0279......Page 295 p0280......Page 296 p0281......Page 297 p0282......Page 298 p0283......Page 299 p0284......Page 300 p0285......Page 301 p0286......Page 302 p0287......Page 303 p0288......Page 304 p0289......Page 305 p0290......Page 306 p0291......Page 307 p0292......Page 308 p0293......Page 309 p0294......Page 310 p0295......Page 311 p0296......Page 312 p0297......Page 313 p0298......Page 314 p0299......Page 315 p0300......Page 316 p0301......Page 317 p0302......Page 318 p0303......Page 319 p0304......Page 320 p0305......Page 321 p0306......Page 322 p0307......Page 323 p0308......Page 324 p0309......Page 325 p0310......Page 326 p0311......Page 327 p0312......Page 328 p0313......Page 329 p0314......Page 330 p0315......Page 331 p0316......Page 332 p0317......Page 333 p0318......Page 334 p0319......Page 335 p0320......Page 336 p0321......Page 337 p0322......Page 338 p0323......Page 339 p0324......Page 340 p0325......Page 341 p0326......Page 342 p0327......Page 343 p0328......Page 344 p0329......Page 345 p0330......Page 346 p0331......Page 347 p0332......Page 348 p0333......Page 349 p0334......Page 350 p0335......Page 351 p0336......Page 352 p0337......Page 353 p0339......Page 355 p0340......Page 356 p0341......Page 357 p0342......Page 358 p0343......Page 359 p0344......Page 360 p0345......Page 361 p0346......Page 362 p0347......Page 363 p0348......Page 364 p0349......Page 365 p0350......Page 366 p0351......Page 367 p0352......Page 368 p0353......Page 369 p0354......Page 370 p0355......Page 371 p0356......Page 372 p0357......Page 373 p0358......Page 374 p0359......Page 375 p0360......Page 376 p0361......Page 377 p0362......Page 378 p0363......Page 379 p0364......Page 380 p0365......Page 381 p0366......Page 382 p0367......Page 383 p0368......Page 384 p0369......Page 385 p0370......Page 386 p0371......Page 387 p0372......Page 388 p0373......Page 389 p0374......Page 390 p0375......Page 391 p0376......Page 392 p0377......Page 393 p0378......Page 394 p0379......Page 395 p0380......Page 396 p0381......Page 397 p0382......Page 398 p0383......Page 399 p0384......Page 400 p0385......Page 401 p0386......Page 402 p0387......Page 403 p0388......Page 404 p0389......Page 405 p0390......Page 406 p0391......Page 407 p0392......Page 408 p0393......Page 409 p0394......Page 410 p0395......Page 411 p0396......Page 412 p0397......Page 413 p0398......Page 414 p0399......Page 415 p0400......Page 416 p0401......Page 417 p0402......Page 418 p0403......Page 419 p0404......Page 420 p0405......Page 421 p0406......Page 422 p0407......Page 423 p0408......Page 424 p0409......Page 425 p0410......Page 426 p0411......Page 427 p0412......Page 428 p0413......Page 429 p0414......Page 430 p0415......Page 431 p0416......Page 432 p0417......Page 433 p0418......Page 434 p0419......Page 435 p0420......Page 436 p0421......Page 437 p0422......Page 438 p0423......Page 439 p0424......Page 440 p0425......Page 441 p0426......Page 442 p0427......Page 443 p0428......Page 444 p0429......Page 445 p0430......Page 446 p0431......Page 447 p0432......Page 448 p0433......Page 449 p0434......Page 450 p0435......Page 451 p0436......Page 452 p0437......Page 453 p0438......Page 454 p0439......Page 455 p0440......Page 456 p0441......Page 457 p0442......Page 458 p0443......Page 459 p0444......Page 460 p0445......Page 461 p0446......Page 462 p0448......Page 464 p0449......Page 465 p0450......Page 466 p0451......Page 467 p0452......Page 468 p0453......Page 469 p0454......Page 470 p0455......Page 471 p0456......Page 472 p0457......Page 473 p0458......Page 474 p0459......Page 475 p0460......Page 476 p0461......Page 477 p0462......Page 478 p0463......Page 479 p0464......Page 480 p0465......Page 481 p0466......Page 482 p0467......Page 483 p0468......Page 484 p0469......Page 485 p0470......Page 486 p0471......Page 487 p0472......Page 488 p0473......Page 489 p0474......Page 490 p0475......Page 491 p0476......Page 492 p0477......Page 493 p0478......Page 494 p0479......Page 495 p0480......Page 496 p0481......Page 497 p0482......Page 498 p0483......Page 499 p0484......Page 500 p0485......Page 501 p0486......Page 502 p0487......Page 503 p0488......Page 504 p0489......Page 505 p0490......Page 506 p0491......Page 507 p0492......Page 508 p0493......Page 509 p0494......Page 510 p0495......Page 511 p0496......Page 512 p0497......Page 513 p0498......Page 514 p0499......Page 515 p0500......Page 516 p0501......Page 517 p0502......Page 518 p0503......Page 519 p0504......Page 520 p0505......Page 521 p0506......Page 522 p0507......Page 523 p0508......Page 524 p0509......Page 525 p0510......Page 526 p0511......Page 527 p0512......Page 528 p0513......Page 529 p0514......Page 530 p0515......Page 531 p0516......Page 532 p0517......Page 533 p0518......Page 534 p0519......Page 535 p0520......Page 536 p0521......Page 537 p0522......Page 538 p0523......Page 539 p0524......Page 540 p0525......Page 541 p0526......Page 542 p0527......Page 543 p0528......Page 544 p0529......Page 545 p0530......Page 546 p0531......Page 547 p0532......Page 548 p0533......Page 549 p0534......Page 550 p0535......Page 551 p0536......Page 552 p0537......Page 553 p0538......Page 554 p0539......Page 555 p0540......Page 556 p0541......Page 557 p0542......Page 558 p0543......Page 559 p0544......Page 560 p0545......Page 561 p0546......Page 562 p0547......Page 563 p0548......Page 564 p0549......Page 565 p0550......Page 566 p0551......Page 567 p0552......Page 568 p0553......Page 569 p0554......Page 570 p0555......Page 571 p0556......Page 572 p0557......Page 573 p0558......Page 574 p0559......Page 575 p0560......Page 576 p0561......Page 577 p0562......Page 578 p0563......Page 579 p0564......Page 580 p0565......Page 581 p0566......Page 582 p0567......Page 583 p0568......Page 584 p0569......Page 585 p0570......Page 586 p0571......Page 587 p0572......Page 588 p0573......Page 589 p0574......Page 590 p0575......Page 591 p0576......Page 592 p0577......Page 593 p0578......Page 594 p0579......Page 595 p0580......Page 596 p0581......Page 597 p0582......Page 598 p0583......Page 599 p0584......Page 600 p0585......Page 601 p0586......Page 602 p0587......Page 603 p0588......Page 604 p0589......Page 605 p0590......Page 606 p0591......Page 607 p0592......Page 608 p0593......Page 609 p0594......Page 610 p0595......Page 611 p0596......Page 612 p0597......Page 613 p0598......Page 614 p0599......Page 615 p0600......Page 616 p0601......Page 617 p0602......Page 618 p0603......Page 619 p0604......Page 620 p0605......Page 621 p0606......Page 622 p0607......Page 623 p0608......Page 624 p0609......Page 625 p0610......Page 626 p0611......Page 627 p0612......Page 628 p0613......Page 629 p0614......Page 630 p0615......Page 631 p0616......Page 632 p0617......Page 633 p0618......Page 634 p0619......Page 635 p0620......Page 636 p0621......Page 637 p0622......Page 638 p0623......Page 639 p0624......Page 640 p0625......Page 641 p0626......Page 642 p0627......Page 643 p0628......Page 644 p0629......Page 645 p0630......Page 646 p0631......Page 647 p0632......Page 648 p0633......Page 649 p0634......Page 650 p0635......Page 651 p0636......Page 652 p0637......Page 653 p0638......Page 654 p0639......Page 655 p0640......Page 656 p0641......Page 657 p0642......Page 658 p0643......Page 659 p0644......Page 660 p0645......Page 661 p0646......Page 662 p0647......Page 663 p0648......Page 664 p0649......Page 665 p0650......Page 666 p0651......Page 667 p0652......Page 668 p0653......Page 669 p0654......Page 670 p0655......Page 671 p0656......Page 672 p0657......Page 673 p0658......Page 674 p0659......Page 675 p0660......Page 676 p0661......Page 677 p0662......Page 678 p0663......Page 679 p0664......Page 680 p0665......Page 681 p0666......Page 682 p0667......Page 683 p0668......Page 684 p0669......Page 685 p0670......Page 686 p0671......Page 687 p0672......Page 688 p0673......Page 689 p0674......Page 690 p0675......Page 691 p0676......Page 692 p0677......Page 693 p0678......Page 694 p0679......Page 695 p0680......Page 696 p0681......Page 697 p0682......Page 698 p0683......Page 699 p0684......Page 700 p0685......Page 701 p0686......Page 702 p0687......Page 703 p0688......Page 704 p0689......Page 705 p0690......Page 706 p0691......Page 707 p0692......Page 708 p0693......Page 709 p0694......Page 710 p0695......Page 711 p0696......Page 712 p0697......Page 713 p0698......Page 714 p0699......Page 715 p0700......Page 716 p0701......Page 717 p0702......Page 718 p0703......Page 719 p0704......Page 720 p0705......Page 721 p0706......Page 722 p0707......Page 723 p0708......Page 724 p0709......Page 725 p0710......Page 726 p0711......Page 727 p0712......Page 728 p0713......Page 729 p0714......Page 730 p0715......Page 731 p0716......Page 732 p0717......Page 733 p0718......Page 734 p0719......Page 735 p0720......Page 736 p0721......Page 737 p0722......Page 738 p0723......Page 739 p0724......Page 740 p0725......Page 741 p0726......Page 742 p0727......Page 743 p0728......Page 744 p0729......Page 745 p0730......Page 746 p0731......Page 747 p0732......Page 748 p0733......Page 749 p0734......Page 750 p0735......Page 751 p0736......Page 752 p0737......Page 753 p0738......Page 754 p0739......Page 755 p0740......Page 756 p0741......Page 757 p0742......Page 758 p0743......Page 759 p0744......Page 760 p0745......Page 761 p0746......Page 762 p0747......Page 763 p0748......Page 764 p0749......Page 765 p0750......Page 766 p0751......Page 767 p0752......Page 768 p0753......Page 769 p0754......Page 770 p0755......Page 771 p0756......Page 772 p0757......Page 773 p0758......Page 774 p0759......Page 775 p0760......Page 776 p0761......Page 777 p0762......Page 778 p0763......Page 779 p0764......Page 780 p0765......Page 781 p0766......Page 782 p0767......Page 783 p0768......Page 784 p0769......Page 785 p0770......Page 786 p0771......Page 787 p0772......Page 788 p0773......Page 789 p0774......Page 790 p0775......Page 791 p0776......Page 792 p0777......Page 793 p0778......Page 794 p0779......Page 795 p0780......Page 796 p0781......Page 797 p0782......Page 798 p0783......Page 799 p0784......Page 800 p0785......Page 801 p0786......Page 802 p0787......Page 803 p0788......Page 804 p0789......Page 805 p0790......Page 806 p0791......Page 807 p0792......Page 808 p0793......Page 809 p0794......Page 810 p0795......Page 811 p0796......Page 812 p0797......Page 813 p0798......Page 814 p0799......Page 815 p0800......Page 816 p0801......Page 817 p0802......Page 818 p0803......Page 819 p0804......Page 820 p0805......Page 821 p0806......Page 822 p0807......Page 823 p0808......Page 824 p0809......Page 825 p0810......Page 826 p0811......Page 827 p0812......Page 828 p0813......Page 829 p0814......Page 830 p0815......Page 831 p0816......Page 832 p0817......Page 833 p0818......Page 834 p0819......Page 835 p0820......Page 836 p0821......Page 837 p0822......Page 838 p0823......Page 839 p0824......Page 840 p0825......Page 841 p0826......Page 842 p0827......Page 843 p0828......Page 844 p0829......Page 845 p0830......Page 846 p0831......Page 847 p0832......Page 848 p0833......Page 849 p0834......Page 850 p0835......Page 851 p0836......Page 852 p0837......Page 853 p0838......Page 854 p0839......Page 855 p0840......Page 856 p0841......Page 857 p0842......Page 858 p0843......Page 859 p0844......Page 860 p0845......Page 861 p0846......Page 862 p0847......Page 863 p0848......Page 864 p0849......Page 865 p0850......Page 866 p0851......Page 867 p0852......Page 868 p0853......Page 869 p0854......Page 870 p0855......Page 871 p0856......Page 872 p0857......Page 873 p0858......Page 874 p0859......Page 875 p0860......Page 876 p0861......Page 877 p0862......Page 878 p0863......Page 879 p0864......Page 880 p0865......Page 881 p0866......Page 882 p0867......Page 883 p0868......Page 884 p0869......Page 885 p0870......Page 886 p0871......Page 887 p0872......Page 888 p0873......Page 889 p0874......Page 890 p0875......Page 891 p0876......Page 892 p0877......Page 893 p0878......Page 894 p0879......Page 895 p0880......Page 896 p0882......Page 898 p0883......Page 899 p0884......Page 900 p0885......Page 901 p0886......Page 902 p0887......Page 903 p0888......Page 904 p0889......Page 905 p0890......Page 906 p0891......Page 907 p0892......Page 908 p0893......Page 909 p0894......Page 910 p0895......Page 911 p0896......Page 912 p0897......Page 913 p0898......Page 914 p0899......Page 915 p0900......Page 916 p0901......Page 917 p0902......Page 918 p0903......Page 919 p0904......Page 920 p0905......Page 921 p0906......Page 922 p0907......Page 923 p0908......Page 924 p0909......Page 925 p0910......Page 926 p0911......Page 927 p0912......Page 928 p0913......Page 929 p0914......Page 930 p0915......Page 931 p0916......Page 932 p0917......Page 933 p0918......Page 934 p0919......Page 935 p0920......Page 936 p0921......Page 937 p0922......Page 938 p0923......Page 939 p0924......Page 940 p0925......Page 941 p0926......Page 942 p0927......Page 943 p0928......Page 944 p0929......Page 945 p0930......Page 946 p0931......Page 947 p0932......Page 948 p0933......Page 949 p0934......Page 950 p0935......Page 951 p0936......Page 952 p0937......Page 953 p0938......Page 954 p0939......Page 955 p0940......Page 956 p0941......Page 957 p0942......Page 958 p0943......Page 959 p0944......Page 960 p0945......Page 961 p0946......Page 962 p0947......Page 963 p0948......Page 964 p0949......Page 965 p0950......Page 966 p0951......Page 967 p0952......Page 968 p0953......Page 969 p0954......Page 970 p0955......Page 971 p0956......Page 972 p0957......Page 973 p0958......Page 974 p0959......Page 975 p0960......Page 976 p0961......Page 977 p0962......Page 978 p0963......Page 979 p0964......Page 980 p0965......Page 981 p0966......Page 982 p0967......Page 983 p0968......Page 984 p0969......Page 985 p0970......Page 986 p0971......Page 987 p0972......Page 988 p0973......Page 989 p0974......Page 990 p0975......Page 991 p0976......Page 992 p0977......Page 993 p0978......Page 994 p0979......Page 995 p0980......Page 996 p0981......Page 997 p0982......Page 998 p0983......Page 999 p0984......Page 1000 p0985......Page 1001