<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> <html> <head> <link href="https://bactra.org/plain-style.css" rel="stylesheet" type="text/css"> <title>Computational Complexity</title>        </head> <body>   <P> <P></P><!-- Access to MathJax through the version I'm hosting on bactra.org !--><!-- but only IF mathmode is activated via meta_mathmode !-->  <script> window.MathJax = {  tex: {    inlineMath: [['$','$'], ['\\(','\\)']],    processEscapes: true,    autoload: {      color: [],      colorv2: ['color']    },    packages: {'[+]': ['noerrors']}  },  options: {    ignoreHtmlClass: 'tex2jax_ignore',    processHtmlClass: 'tex2jax_process'  },  loader: {    load: ['[tex]/noerrors']  }};</script>      <cite><a href="http://bactra.org/notebooks">Notebooks</a></cite> <div class="text"><div class="left"><h2>Computational Complexity</h2> <i><a href="faq.html#5.4">Last update</a>: 21 Apr 2025 21:17</i><br><i><a href="faq.html#5.4">First version</a>: 23 November 2024</i> <hr> <P>  <P>Yet Another Inadequate Placeholder <P>--- Or, rather, I've said most of what I have to say in the form of a review of a <a href="http://bactra.org/reviews/nature-of-computation.html">truly excellent book</a>. <P><em>Things to learn</em>: Finally get a handle on all the time complexityclasses that are finer than the P/NP distinction.  The space classes.  Circuitcomplexity, and how it relates to time and space complexity.  Information-based complexity.  Connections to / analogies with sample complexity in <a href="learning-theory.html">statistical learning theory</a>.  "Phasetransitions" between complexity classes, and the analogy tophysical <a href="phase-transitions.html">phase transitions</a>. <ul>See also:	<li><a href="computation.html">Computation, Automata, Languages</a>	<li><a href="complexity-measures.html">Complexity Measures</a>	<li><a href="learning-theory.html">Learning Theory (Formal, Computational or Statistical)</a>	<li><a href="optimization.html">Optimization</a> [Where I stash most references on the computational complexity of optimization algorithms, except for those which I arbitrarily decide have a broader scope and include here]	<li><a href="planned-economies.html">Planned Economies</a>	</ul>... though really there are many, many topics where computational-complexity considerations come into play (e.g., <a href="community-discovery.html">community discovery in networks</a>) <ul>Recommended, big picture:	<li>David Harel, <cite>The Science of Computing: Exploring the Nature and Power of Algorithms</cite>	<li>Cristopher Moore and Stephan Mertens, <cite><a href="http://www.nature-of-computation.org/">The Nature of Computation</a></cite> [Cris and Stephan were kind enough to let me read this in manuscript; it's magnificent.  Review: <a href="http://bactra.org/reviews/nature-of-computation.html">Intellects Vast and Warm and Sympathetic</a>]	</ul>  <ul>Recommended, close ups:	<li>Scott Aaronson, "Why Philosophers Should Care About Computational Complexity", <a href="http://arxiv.org/abs/1108.1791">arxiv:1108.1791</a>	<li>Andrei Broder and Jorge Stolfi, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.116.9158">Pessimal Algorithms and Simplexity Analysis</a>	<li>Christos H. Papadimitriou and Kenneth Steiglitz, <cite>Combinatorial Optimization: Algorithms and Complexity</cite>	<li>J. F. Traub and A. G. Werschulz, <cite><a href="http://bactra.org/weblog/algae-2014-09.html#ibc">Complexity and Information</a></cite>	<li>J. F. Traub and H. Wozniakowski, "Persepctives on Information-BasedComplexity," <cite>Bulletin of the American MathematicalSociety</cite> <strong>26</strong> (1992): 29--52, <ahref="http://arxiv.org/abs/math.NA/9201269/">math.NA/9201269</a>	</ul> <ul>To read:	<li>Sanjeev Arora and Boaz Barak, <cite><a href="https://doi.org/10.1017/CBO9780511804090">Computational Complexity: A Modern Approach</a></cite>	<li>David Gamarnik, Cristopher Moore, Lenka Zdeborov&aacute;, "Disordered Systems Insights on Computational Hardness", <a href="http://arxiv.org/abs/2210.08312">arxiv:2210.08312</a>	<li>Odd Goldreich, <cite><a href="https://doi.org/10.1017/CBO9780511804106">Computational Complexity: A Conceptual Perspective</a></cite>	<li>Raymond Greenlaw, H. James Hoover, Walter L. Ruzzo, <cite><a href="https://doi.org/10.1093/oso/9780195085914.001.0001">Limits to Parallel Computation: P-Completeness Theory</a></cite>	<Li>David Harel, <cite>Computers Ltd: What They Really Can't Do</cite> [Unless this is just a variant title for <cite>Science of Computing</cite>?]	<li>Dorit Hochbaum, <citE>Approximation Algorithms for NP-HardProblems</cite>	<li>Johannes Kobler and Rainer Schuler, "Average-case intractabilityvs. worst-case intractability", <ahref="http://dx.doi.org/10.1016/j.ic.2003.05.002"><citE>Information andComputation</cite> <strong>190</strong> (2004): 1--17</a>	<li>Eyal Kushilevitz and Noam Nisan, <cite><a href="https://doi.org/10.1017/CBO9780511574948">Communication Complexity</a></cite>	<li>Marc Mezard and Andrea Montanari, <cite><a href="https://doi.org/10.1093/acprof:oso/9780198570837.001.0001">Information, Physics, and Computation</a></cite>	<li>Istv&aacute;n Mikl&oacute;s, <cite>Computational Complexity of Counting and Sampling</cite>	<li>Allon Percus, Gabriel Istrate and Cristopher Moore (eds.), <cite><a href="https://doi.org/10.1093/oso/9780195177374.001.0001">Computational Complexity and Statistical Physics</a></cite>	<li>Leszek Plaskota, <cite><a href="https://doi.org/10.1017/CBO9780511600814">Noisy Information and Computational Complexity</a></cite> [<a href="https://www.mimuw.edu.pl/~leszekp/dydaktyka/zlozonosc/MyBook.pdf">PDF via Dr. Plaskota</a>]	<li>Anup Rao and Amir Yehudayoff, <cite><a href="https://doi.org/10.1017/9781108671644">Communication Complexity: and Applications</a></cite>	<li>Wojciech Szpankowski, <cite>Average Case Analysis of Algorithms onSequences</cite>[<a href="http://www.cs.purdue.edu/homes/spa/book.html">Preprint version</a>]	<li>Vijay V. Vazirani, <cite><a href="https://doi.org/10.1007/978-3-662-04565-7">Approximation Algorithms</a></cite> [<a href="https://ics.uci.edu/~vazirani/book.pdf">PDF via Prof. Vazirani</a>]	<li>Herbert S. Wilf, <citE><a href="https://www2.math.upenn.edu/~wilf/AlgComp.html">Algorithms and Complexity</a></cite>	</ul>  </p> </div></div> <hr> <div class="footer"><P><a href="http://bactra.org/notebooks/computational-complexity.html">permanent link for thisnote</a> &nbsp; <a href="http://bactra.org/notebooks/computational-complexity.rss">RSS feed for thisnote</a></P></div><div class="foot"> <center> <cite><a href="http://bactra.org/notebooks">Notebooks</a></cite>: &nbsp; <a href="http://www.blosxom.com/">Powered by Blosxom</a> </center> </div> </body></html>