Computational Complexity

I'm the author of this article. If you ask a complexity theorist, they will tell you that they did in fact have a general intuition that certain problems require space close to to linear in time to solve (see e.g., Ryan's comment #22 on Scott Aaronson's blog post about the result: https://scottaaronson.blog/?p=8680, and the comments after that). The most intuitive way to see this is in a circuit/DAG picture, where the goal is to get from the input nodes of the graph to the output nodes. Some graphs are very "wide": cut the graph at some intermediate point, and there will be a lot of edges crossing the cut, each of which represents some information from an earlier stage in the computation that you'll need to remember to get to the output. Ryan's first result is a general-purpose method for doing any computation, even ones whose graph structure looks like this, in asymptotically far less space. That is precisely what makes the result so surprising!

My article was quite explicit in multiple places that the universal/comprehensive character of the result was that counterintuitive part:

- In the first paragraph: "memory was more powerful than computer scientists believed: A small amount would be as helpful as a lot of time in all conceivable computations."

- Further down in the introduction, in the passage you quoted: "Until now, the only known algorithms for accomplishing certain tasks required an amount of space roughly proportional to their runtime, and researchers had long…

Every agent tries to understand (or perhaps "dualize") its environment.

I both like and dislike theories of mind that describe the brain in terms of n-veiled solipsism. But I generally like them because of the specific (decision-theoretic) statements they make about how an agent is defining its environment.

What's striking to me about life on earth -- mostly humanity, but also the larger notions of noo-/biosphere -- is that, so far, it doesn't match up to our larger-scale evidence about how <things in general> define <their environments>.

We have managed to define our environment in a fashion which is scale-agnostic, at least with respect to the measurement of physical accumulations of stuff. We readily form metaphors between:

(a) things in our locale,

(b) things in the huge,

(c) things in the tiny, and

(d) things in the meta (read: math/pattern).

I think the worst thing we can do -- as engineers or scientists or mathematicians or even metaphysicians -- is to presume that any of |a-d| generate the others "in reality". (I just did a bit of that when I implicitly defined "larger-scale evidence" as "most legitimate evidence".)

In the categorical sense of arrow-reversal-without-structural-change[0], models of |a-d| are dual to any notion of 'environment' we can imagine. That doesn't suggest determinism, but it does offload every variation on the question of free will into a(n empty) simulationist argument whose limit is some computational infinity, like an omni-* deity…

A few random comments:

• Obviously, this is typeset with TeX.

• Though originally Knuth created TeX for books rather than single-page articles, he's most familiar with this tool so it's unsurprising that he'd use it to just type something out. (I remember reading somewhere that Joel Spolsky, who was PM on Excel, used Excel for everything.)

• To create the PDF, where most modern TeX users might just use pdftex, he seems to first created a DVI file with tex (see the PDF's title “huang.dvi”), then gone via dvips (version 5.98, from 2009) to convert to PostScript, then (perhaps on another computer?) “Acrobat Distiller 19.0 (Macintosh)” to go from PS to PDF.

• If you find it different from the “typical” paper typeset with LaTeX, remember that Knuth doesn't use LaTeX; this is typeset in plain TeX. :-) Unlike LaTeX which aims to be a “document preparation system” with “logical”/“structured” (“semantic”) markup rather than visual formatting, for Knuth TeX is just a tool; typically he works with pencil and paper and uses a computer/TeX only for the final typesetting, where all he needs is to control the formatting.

• Despite being typeset with TeX which is supposed to produce beautiful results, the document may appear very poor on your computer screen (at least it did when I first viewed it on a Linux desktop; on a Mac laptop with Retina display it looks much better though somewhat “light”). But if you zoom in quite a bit, or print it, it looks great. The reason is that Knuth…

You got it! By approximate category and in no particular order:

## MISCELLANEOUS

- [Low Tech Magazine](https://solar.lowtechmagazine.com), a solar-powered website showcasing the amazing low-tech things you can do with a little ingenuity,

- [Stephen Wolfram's Blog](https://writings.stephenwolfram.com) on math, compsci, and everything else,

- [Cool Macrophotography](https://www.barrywebbimages.co.uk/Images/Macro/Slime-Moulds-Myxomycetes) for amazing pictures of tiny things (WARNING: Time Sink!),

## COMPUTER SCIENCE

- [While-True-Do](https://blog.while-true-do.io) has lots of stuff on Linux administration and self-hosting,

- [Backend Banter](https://www.backendbanter.fm) for a great podcast on backend development,

- [Two Wrongs](https://two-wrongs.com) for statistics and functional programming,

- [Math ∩ Programming](https://www.jeremykun.com/) where math and programming intersect! Written by a Googler...

- [Paul Bourke's site](https://paulbourke.net/) where you can get happily lost exploring old pages on every topic CS touches,

- [Jason Punyon's blog](https://jasonpunyon.com) for some fun algorithms and things,

- [Yossi Kreinin's blog](https://yosefk.com/blog) for C, Python, and plenty of non-technical topics,

- [Adrian Sampson's academic blog](https://www.cs.cornell.edu/~asampson/blog) for an academic's perspective,

- [Cool polyhedra viewer project](https://georgehart.com/virtual-polyhedra/vp.html) if you like geometry,

- [Another academic blog on…

This is technically not an O(n lg n) algorithm. Any O(n lg n) polynomial multiplication algorithm can be trivially turned into an O(n lg n) multiplication algorithm (just throw in some carries at the end), but O(n lg n) multiplication is an open problem.

In this case the issue is that you need more and more precision for the FFT as the inputs get larger, or else you'll get the wrong answer. I think it ends up being an O(n log^2 n) algorithm. Still pretty good; worth knowing about for sure. The constant factor on the precision might be bad enough that you can trigger the problem for reasonable inputs if you're using floats (e.g. a million coefficients, instead of an octillion coefficients).

On the other hand, many algorithms and data structures have hidden logarithmic factors (e.g. hash tables, sorting) that we ignore [1]. YMMV.

1: http://blog.computationalcomplexity.org/2009/05/shaving-logs-with-unit-cost.html

Relevant blog post by an actual complexity theorist: https://blog.computationalcomplexity.org/2018/10/if-pnp-then-we-have-alg-for-sat.html.

>The following does not quite show it can't happen but it does give one pause: an old result of Levin's shows that there is a program you could write NOW such that if P=NP then this program decides SAT except for a finite number of formulas (all of which are NOT in SAT) and can be proven to work in poly time (I will later give three pointers to proofs). The finite number of formulas is why the people above may still be right. But only a finite number- seems like a weak kind of nonconstructive.

So, based on this post, it is actually not known that P=NP implies existence of polynomial time algorithm for deciding SAT. The universal search idea only yields a polynomial time algorithm that decides SAT for all but a finite number of formulas.