The computational power of salient CSP solutions

Charles Bennett was one of the first to think concretely about reversible computation, and became a pioneer of both quantum computation and quantum cryptography. He was a co-discoverer of quantum teleportation and co-developer of methods to transmit both classical and quantum information over noisy channels. He is thus good to think about when we discuss noise in quantum computation. We have mentioned that he is one of Aram Harrow’s partners on the Quantum Pontiff blog.

Today, however, we discuss his seminal non-quantum concept of logical depth. We ask about possible computational benefits of depth, with reference to a recently solved coloring problem on 17×17 and 18×18 grids.

Roughly speaking, a string is (logically or computationally) deep if it has a short description, but every attempt to generate it from a short description requires a large amount of time. Open problems in computational complexity prevent general proofs of the “requires” part, but we can give intuitive examples of deep strings subject to common beliefs. Here is a family of such strings whose descriptions require only giving a length in binary, plus bits to specify a program which is finite and independent of .

the lexicographically first string in on which achieves its worst-case running time on binary inputs of length .

This description has bits, but unpacking to find the actual string ostensibly requires running on exponentially many strings, for time at least . Another source of deep strings is solutions to constraint-satisfaction problems (CSP’s) that are easily specified and hard to solve. We covered the Kolmogorov complexity of solutions to problems initially here.

Murray Gell-Mann emphasized a similar concept of depth in his popular book The Quark and the Jaguar, in which deep structures arise from millennia of evolution, using “evolution” in several senses. Concepts of this kind were formalized in this paper by Luis Antunes, Lance Fortnow, Dieter Van Melkebeek, and N. Variyam Vinodchandran. We wonder what computational power deep structures may subsequently have for solving problems.

Is the New 17×17 Coloring Deep?

Bill Gasarch recently announced on the blog “Computational Complexity” a solution to a long-open problem about colorings. The general problem is to color the vertices of an grid with colors so that no four vertices that form a rectangle (with sides parallel to the axes) receive the same color. This is a prominent instance of Ramsey Theory—see these slides by Bill with Stephen Fenner, Charles Glover, and Semmy Purewal for more.

The case 17×17 for 4-colorings had eluded solution for so long that Bill posted a $289 reward for such a coloring. Bernd Steinberg and Christian Posthoff, both long active in computer chess and solving, collected it last week, and found a 4-coloring of the 18×18 grid without monochromatic rectangles to boot.

Here is the 17×17 coloring, as illustrated by Brent Yorgey on his blog “The Math Less Traveled” which we keep in our sidebar.

It is already something of a headache to verify that none of the 18,496 relevant rectangles is monochrome, though Bill says he did so by hand. But we are talking about the complexity of generating it from the short description of the problem. Apparently Steinbach and Posthoff needed much computer time as well as ingenuity, though full details of how they found it may await their paper appearing at the 42nd IEEE Symposium on Multiple-Valued Logic (ISMVL) in May.

Not as Easy as Pi?

Is the coloring deep? One issue is that it is far from unique. As noted in this StackExchange item, one can permute the rows, columns, and colors arbitrarily, and also flip the grid along one diagonal. The one shown here is a top-to-bottom flip with different colors. However, now that we know that the set of good colorings is non-empty, we can single out a unique member by the same “lexicographically first” trick as above for input strings, regarding the 4-coloring as a binary string in row-by-row order. This gives us a unique string .

The resulting string then seems to qualify as deep—assuming we can specify the problem it solves in under 500 bits, say. If we think about solutions for other borderline cases of we certainly get a deep family. Does this make the family useful? Can strings like this be used as an oracle to de-randomize problems in ? What randomness properties does the coloring have? Certainly we would hope that since a lot of computational effort was poured into creating it, some computational power can be tapped from it.

Note that for a solution to be deep we need two things: The problem it solves must be “salient”—which means prominent in a way that simple considerations make it easy to specify—but the solution itself must be complex. The digits of are salient, but they are not deep. Indeed they are computable by a kind of fast algorithm called a “spigot algorithm.” Although they are believed to satisfy many statistical tests of randomness, a study in 2005 by researchers at Purdue found cases where they are not as effective as various feasibly-computable pseudo-random number generators. Even where they compete with random strings there may be limits on power—note how this aligns with Bennett’s famous paper with John Gill on random oracles, and with work we covered here. We wonder whether strings such as the 17×17 coloring that were much harder to obtain can pack more punch.

Open Problems

The coloring does have monochromatic rectangles that are diagonally aligned, for instance the two yellow pips flanking the bottom-left corner and the two a knight’s-move from the upper right corner. Is it possible to avoid these rectangles too? with how many more colors? Pursuing the same kind of statistical analysis as by Brian Hayes here, are there fewer diagonally-aligned monochrome rectangles than in a random 4-coloring? If so, what does that say about correlations between (approximate) solutions of different CSP’s?

Do you see anything in the coloring, perhaps an outline of Abraham Lincoln’s head for today, or XXX for Valentine’s Day? Dick thought the latter on turning the picture 90 degrees right. Do deep designs give a higher tendency to see or imagine interesting patterns?