The DOI matches its Crossref record.
Introduction to the Theory of Computation
Abstract
"Michael Sipser's philosophy in writing this book is simple: make the subject interesting and relevant, and the students will learn. His emphasis on unifying computer science theory - rather than offering a collection of low-level details - sets the book apart, as do his intuitive explanations. Throughout the book, Sipser - a noted authority on the theory of computation - builds students' knowledge of conceptual tools used in computer science, the aesthetic sense they need to create elegant systems, and the ability to think through problems on their own. INTRODUCTION TO THE THEORY OF COMPUTATION provides a mathematical treatment of computation theory grounded in theorems and proofs. Proofs are presented with a "proof idea" component to reveal the concepts underpinning the formalism. Algorithms are presented using prose instead of pseudocode to focus attention on the algorithms themselves, rather than on specific computational models. Topic coverage, terminology, and order of presentation are traditional for an upper-level course in computer science theory. Users of the Preliminary Edition (now out of print) will be interested to note several new chapters on complexity theory: Chapter 8 on space complexity; Chapter 9 on provable intractability, and Chapter 10 on advanced topics, including approximation algorithms, alternation, interactive proof systems, cryptography, and parallel computing." -- Publisher's description.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
Quantum Algorithm for Linear Systems of Equations
Harrow, A. W., Hassidim, A., & Lloyd, S. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.150502 · Cited by 3,325
“[29] M.”
BackgroundUniversally composable security: a new paradigm for cryptographic protocols
Canetti, R. (2001) · Proceedings 42nd IEEE Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959888 · Cited by 3,309
(2015) · Cited by 2,857
Gühne, O., & Tóth, G. (2009) · Physics Reports · doi:10.1016/j.physrep.2009.02.004 · Cited by 2,401
Expander graphs and their applications
Hoory, S., Linial, N., & Wigderson, A. (2006) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-06-01126-8 · Cited by 1,723
On the (Im)possibility of Obfuscating Programs
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., & Yang, K. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44647-8_1 · Cited by 1,286
Most Tensor Problems Are NP-Hard
Hillar, C. J., & Lim, L.-H. (2013) · Journal of the ACM · doi:10.1145/2512329 · Cited by 1,099
Procedural modeling of buildings
Müller, P., Wonka, P., Haegler, S., Ulmer, A., & Van Gool, L. (2006) · ACM Transactions on Graphics · doi:10.1145/1141911.1141931 · Cited by 950
Mitra, P., & Bokil, H. (2007) · doi:10.1093/acprof:oso/9780195178081.001.0001 · Cited by 842
Optimal structure, market dynamism, and the strategy of simple rules
Davis, J. P., Eisenhardt, K. M., & Bingham, C. B. (2009) · Administrative Science Quarterly · doi:10.2189/asqu.2009.54.3.413 · Cited by 804
“Like computational complexity, complexity can be conceptualized as the minimum number of correct steps that are needed to execute a plan (Simon, 1962; Sipser, 1997).”
BackgroundA rewriting system for convex optimization problems
Agrawal, A., Verschueren, R., Diamond, S., & Boyd, S. (2018) · Journal of Control and Decision · doi:10.1080/23307706.2017.1397554 · Cited by 669
On the (im)possibility of obfuscating programs
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., & Yang, K. (2012) · Journal of the ACM · doi:10.1145/2160158.2160159 · Cited by 595
Fitch, W. T. (2010) · doi:10.1017/cbo9780511817779 · Cited by 594
Vempala, S. (2005) · DIMACS Series in Discrete Mathematics and Theoretical Computer Science · doi:10.1090/dimacs/065 · Cited by 538
Lysyanskaya, A., Rivest, R. L., Sahai, A., & Wolf, S. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-46513-8_14 · Cited by 521
Exploiting coarse-grained task, data, and pipeline parallelism in stream programs
Gordon, M. I., Thies, W., & Amarasinghe, S. (2006) · Proceedings of the 12th international conference on Architectural support for programming languages and operating systems · doi:10.1145/1168857.1168877 · Cited by 512
Limits on fundamental limits to computation
Markov, I. L. (2014) · Nature · doi:10.1038/nature13570 · Cited by 494
Koolen, T., de Boer, T., Rebula, J., Goswami, A., & Pratt, J. (2012) · The International Journal of Robotics Research · doi:10.1177/0278364912452673 · Cited by 483
Di, B., Song, L., & Li, Y. (2016) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2016.2606100 · Cited by 444
Artificial intelligence and computer science in education: From kindergarten to university
Kandlhofer, M., Steinbauer, G., Hirschmugl-Gaisch, S., & Huber, P. (2016) · 2016 IEEE Frontiers in Education Conference (FIE) · doi:10.1109/fie.2016.7757570 · Cited by 437
Optimal Inequalities in Probability Theory: A Convex Optimization Approach
Bertsimas, D., & Popescu, I. (2005) · SIAM Journal on Optimization · doi:10.1137/s1052623401399903 · Cited by 428
Cellular UAV-to-X Communications: Design and Optimization for Multi-UAV Networks
Zhang, S., Zhang, H., Di, B., & Song, L. (2019) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2019.2892131 · Cited by 415
Statistical machine translation
Lopez, A. (2008) · ACM Computing Surveys · doi:10.1145/1380584.1380586 · Cited by 410
Phase Unwrapping in InSAR : A Review
Yu, H., Lan, Y., Yuan, Z., Xu, J., & Lee, H. (2019) · IEEE Geoscience and Remote Sensing Magazine · doi:10.1109/mgrs.2018.2873644 · Cited by 399
An Untethered, Electrostatic, Globally Controllable MEMS Micro-Robot
Donald, B. R., Levey, C. G., McGray, C. D., Paprotny, I., & Rus, D. (2006) · Journal of Microelectromechanical Systems · doi:10.1109/jmems.2005.863697 · Cited by 339
Abstract Syntax Networks for Code Generation and Semantic Parsing
Rabinovich, M., Stern, M., & Klein, D. (2017) · Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/p17-1105 · Cited by 312
A Real-Time Visual Inspection System for Discrete Surface Defects of Rail Heads
Li, Q., & Ren, S. (2012) · IEEE Transactions on Instrumentation and Measurement · doi:10.1109/tim.2012.2184959 · Cited by 299
A survey of active learning in collaborative filtering recommender systems
Elahi, M., Ricci, F., & Rubens, N. (2016) · Computer Science Review · doi:10.1016/j.cosrev.2016.05.002 · Cited by 292
Wakeup scheduling in wireless sensor networks
Keshavarzian, A., Lee, H., & Venkatraman, L. (2006) · Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing · doi:10.1145/1132905.1132941 · Cited by 290
Dowell, R. D., & Eddy, S. R. (2004) · BMC Bioinformatics · doi:10.1186/1471-2105-5-71 · Cited by 280
Bellare, M., Ristenpart, T., Rogaway, P., & Stegers, T. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-05445-7_19 · Cited by 274
Computation with finite stochastic chemical reaction networks
Soloveichik, D., Cook, M., Winfree, E., & Bruck, J. (2008) · Natural Computing · doi:10.1007/s11047-008-9067-y · Cited by 255
Floridi, L. (2016) · SSRN Electronic Journal · doi:10.2139/ssrn.3835211 · Cited by 227
Computability: An introduction to recursive function theory
Cutland, N. (1980) · doi:10.1017/cbo9781139171496 · Cited by 206
What the Near Future of Artificial Intelligence Could Be
Floridi, L. (2019) · Philosophy & Technology · doi:10.1007/s13347-019-00345-y · Cited by 191
Survey on reinforcement learning for language processing
Uc-Cetina, V., Navarro-Guerrero, N., Martin-Gonzalez, A., Weber, C., & Wermter, S. (2023) · Artificial Intelligence Review · doi:10.1007/s10462-022-10205-5 · Cited by 177
A study of heuristic guesses for adiabatic quantum computation
Perdomo-Ortiz, A., Venegas-Andraca, S. E., & Aspuru-Guzik, A. (2011) · Quantum Information Processing · doi:10.1007/s11128-010-0168-z · Cited by 111
A bird's eye view of human language evolution
Berwick, R. C., Beckers, G. J. L., Okanoya, K., & Bolhuis, J. J. (2012) · Frontiers in Evolutionary Neuroscience · doi:10.3389/fnevo.2012.00005 · Cited by 81
Blum, L., & Blum, M. (2022) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2115934119 · Cited by 70
Computational complexity in electronic structure
Whitfield, J. D., Love, P. J., & Aspuru-Guzik, A. (2013) · Phys. Chem. Chem. Phys. · doi:10.1039/c2cp42695a · Cited by 71
Meta-learning of Sequential Strategies
Ortega, P. A., Wang, J. X., Rowland, M., Genewein, T., Kurth-Nelson, Z., Pascanu, R., Heess, N., Veness, J., Pritzel, A., Sprechmann, P., et al. (2019) · arXiv · doi:10.48550/arxiv.1905.03030 · Cited by 47
Castaldo, D., Rosa, M., & Corni, S. (2020) · arXiv · doi:10.48550/arxiv.2007.00368 · Cited by 32
Quantifying the Transition from Python 2 to 3: An Empirical Study of Python Applications
Malloy, B. A., & Power, J. F. (2017) · 2017 ACM/IEEE International Symposium on Empirical Software Engineering and Measurement (ESEM) · doi:10.1109/esem.2017.45 · Cited by 27
Gate-based quantum computing for protein design
Khatami, M. H., Mendes, U. C., Wiebe, N., & Kim, P. M. (2023) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1011033 · Cited by 26
Self-Adapting Reliability in Distributed Software Systems
Brun, Y., Bang, J. Y., Edwards, G., & Medvidovic, N. (2015) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2015.2412134 · Cited by 16
Safwat, I., Li, W., & Wu, X. (2017) · Energies · doi:10.3390/en10111751 · Cited by 14
Irie, K., Csordás, R., & Schmidhuber, J. (2023) · arXiv · doi:10.48550/arxiv.2310.16076 · Cited by 3
Computational Complexity of Quadratic Unconstrained Binary Optimization
Yasuoka, H. (2021) · arXiv · doi:10.48550/arxiv.2109.10048
Metadata
- Authors
- Sipser, M.
- Venue
- ACM SIGACT News
- Published
- 1996-03
- Volume
- 27
- Issue
- 1
- Pages
- 27-29
- ISSN
- 0163-5700 (ISSN-L)
- OpenAlex
- W1994584977
- Cited by
- 2,784
- References
- 0
- FWCI
- 12.37
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.