Jump to ContentJump to Main Navigation
The Nature of Computation - Oxford Scholarship Online
Users without a subscription are not able to see the full content.

The Nature of Computation

Cristopher Moore and Stephan Mertens


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. However, this beauty is often buried underneath layers of unnecessary formalism, and exciting recent results such as interactive proofs, phase transitions, and quantum computing are usually considered too advanced for the typical student. This book bridges these gaps by explaining the deep ideas of theoretical computer science in a clear fashion, making them accessible to non-computer scientists and to computer scientists who fin ... More

Keywords: computational complexity, interactive proofs, phase transitions, quantum computing, theoretical computer science, P vs. NP, optimisation, randomised algorithms, pseudorandomness, Markov chains

Bibliographic Information

Print publication date: 2011 Print ISBN-13: 9780199233212
Published to Oxford Scholarship Online: December 2013 DOI:10.1093/acprof:oso/9780199233212.001.0001


Affiliations are at time of print publication.

Cristopher Moore, author
Computer Science Department and Department of Physics and Astronomy, University of New Mexico, and External Professor, Santa Fe Institute

Stephan Mertens, author
Institute of Theoretical Physics, Otto-von-Guericke University, Magdeburg, and External Professor, Santa Fe Institute