http://www.cse.buffalo.edu/~regan/papers/pdf/Reg02MSFD.pdf

and here:

]]>It seems to me that the “children learning language” is an example of nature being able to come up with a very good heuristic solutions through its use of selection. But the facts that languages change over time, that there are different dialects of the same language, and that children don’t talk exactly like their parents suggest to me that however nature does it, it really is just a heuristic. Nature hasn’t yet proven P = NP.

]]>But we do *not* (presently) possess similarly good representation theories for litotic systems, that is, the broad class of systems that are dynamically concentrated onto small-dimension state-spaces. This class generically includes symplectic systems that are in contact with noisy and/or low temperature reservoirs (such systems being ubiquitous in the real world). Empirically these systems can be simulated efficiently because the accessible regions of state-space are algorithmically compressible, but we do not presently have any very deep/broad understanding of how this concentration occurs (although we do have litotic constructions for have *some* concentration theorems, e.g., positive *P*-representations for arbitrary-*j* thermalized spin systems).

The bottom line: we humans are hot, wet, noisy, algorithmically compressible creatures whose languages are “learnable” precisely because these languages evolved via hot, wet, noisy, algorithmically compressible physical processes.

The above is a quantum systems engineering view, at any rate … many alternative views are equally reasonable … for the very good reason that we don’t at present really know all that much about this class of problem.

Dick Lipton’s blog has a fine essay on this problem, titled *SAT Solvers: Is SAT Hard or Easy?*

Transportation of all forms will be scheduled optimally to move people and goods around quicker and cheaper.

Then later on, he writes:

…we can now solve, in practice, traveling salespeople problems with more than 10,000 cities…

Unless we have really determined salesmen or truck drivers or something, I don’t get it: if we can already solve these optimization problems for 10,000 nodes, what practical good would a P=NP solution be?

As a computational linguist, I also doubt his claim that “Near perfect… language comprehension and translation and all other learning tasks become trivial.” It’s true that generating a machine translation system from a large corpus takes a long time, but that’s not what’s holding us back: we don’t have sufficiently large corpora even for the best language pairs, and we have far from sufficiently large corpora for 99.9% of the pairs. And while there are doubtless better approaches to MT, it’s not at all clear that the problem would be solved by a faster algorithm.

Of course, there might be computational linguists out there who would disagree with me. So: does anyone know where I could find discussion of claims like these? (If P=NP, then X would become trivially easy.)

(BTW, if language comprehension–or better, learning a natural language well enough to comprehend it–is NP-hard, then maybe children are an existence proof that P=NP, since they learn languages so fast!)

]]>On this list, the yellow Swiss book *Die Physiker* looked particularly interesting. Its Wikipedia summary reminds me strongly of Carter Scholz’ excellent and mathematically erudite book *Radiance* … both are dark comedies about science … both are available (in limited preview) on Google Books.

And yes, *Radiance* too has a yellow-themed cover … what’s up with that?

Ah, why mention the awards? Tacky.

]]>The book looks Birkhauser Green to me! It appears to have a cool publisher, too.

]]>Connie pointed out that yellow book covers are a wonderful example of *biophilia* (a term coined by E. O. Wilson to describe the innate human liking for everything that our evolutionary history has conditioned us to like).

It works like this. You go to a library or a bookstore … you pick a book off the shelf … a book that somehow looks enticing … a book with a green or brown background … and a foreground that is banana-yellow … cherry-red … orange-orange … lime-green … blueberry-blue.

Hmmm … when you think about it … what’s more enticing to a primate … than a lusciously ripe, brightly covered fruit … framed by darker green/brown foliage … within easy arm’s reach?

Isn’t this “yellow book” bookbinding aesthetic partly the reason why libraries and bookstores are such comfortable places? They are paradises in which the fruits of intellect are within easy reach!

Connie and I laughed together at these silly notions … but then, hey … we too designed the book cover to accord with the traditional “yellow-book” biophilia-driven aesthetic of publishing … and we shipped those book files this morning off to the printer. Because even when you understand their evolutionary origins, “yellow book”: biophilic traditions demand and deserve respect.

All hail the mighty memoir class of LaTeX, which makes it easy to respect “yellow book” traditions! ðŸ™‚

]]>Why would you prove an infinite collection of statements by showing that they’re susceptible to a particular algorithm, and showing what that algorithm does to them? Are there other examples where people have done this? why an efficient algorithm? who cares if they’re in P, when you’re finally done and know the answer in constant time?

It sounds to me like there is supposed to be some extra property that leads both to the algorithm applying and to being able to understand the infinite family. From this point of view, the algorithm is a detour. It might be a useful detour; for example, if you can prove the algorithm works, you can run it in a finite number of cases. Even if you can’t prove it works, if you want the answer to be Yes and the problem is in NP, as in the example, you can run the algorithm anyhow. Has this been done? I suspect no, and I suspect reason is that the algorithm is supposed to be polynomial in the inputs, but the inputs are big in terms of n. (Also, another obvious question: why do they propose two algorithms? It does seem plausible that it’s useful to prove that a standard heuristic like LP relaxation applies; but a special-purpose algorithm?)

]]>