The Nature of Computation

摘要: Computational complexity is one of the most beautiful fields modern mathematics, and it increasingly relevant to other sciences ranging from physics biology. But this beauty often buried underneath layers unnecessary formalism, exciting recent results like interactive proofs, cryptography, quantum computing are usually considered too "advanced" show typical student. The aim book bridge both gaps by explaining deep ideas theoretical computer science in a clear enjoyable fashion, making them accessible non scientists who finally want understand what their formalisms actually telling. This gives lucid playful explanation field, starting with P NP-completeness. authors explain why vs. NP problem so fundamental, hard resolve. They then lead reader through mazes games; optimization theory practice; randomized algorithms, pseudorandomness; Markov chains phase transitions; outer reaches computing. At every turn, they use minimum providing explanations that accessible. intended for graduates undergraduates, areas have long wanted subject, experts fall love field all over again.