rose.blog

is here. Also I’ve added it to my blogroll.

is here.

Even Elmo is not safe from NP-completeness.

While funny I don’t think this will meet the $1B market threshold any time soon.

Although I like it as a gentle introduction for non-experts.

The standard approach to solving large sets of related problems is to choose a canonical language for describing all of them, and then write a translator that will reduce them to some other canonical language which is then solved.

The descriptive language has to be easy for humans to understand, and the solver language has to be easy for solvers to handle.

The basic idea that all problems are written in a human language and then translated to a low-level language is of course how all computers work; think Java –> Opteron machine language.

OK so what does this have to do with automatic programming? I’m going to make a short detour into a related problem and then circle back to this.

It has to do with methods for solving NP problems. A central idea in the theory of NP-completeness is the concept of reduction. Reduction is a procedure for showing that a given problem is related to another problem in a specific way. The concept is usually used in an academic context for proving that a problem is NP-complete, but there is a recent move to using reduction in practical contexts.

Here’s an example: A very interesting result called Fagin’s theorem shows that any NP problem can be posed in something like SQL with some extensions. So for the NP version of automatic programming, we can use logical declarations to define the specification, and have an automatic translater to a canonical solver language, like SAT (or the two-dimensional Ising model in a magnetic field for those of you paying attention ) for example.

If the solvers used on the canonical solver language are good enough, the cost of doing the translation can in principle be overcome. For NP problems it has usually been assumed that each individual problem is better treated by a heuristic designed specifically for its solution, and that in reducing it to something else (like SAT) you will lose more than you gain.

There are two obvious loopholes in this view. The first is that if a particular solver of a particular NP problem is much better than any other, the cost of reduction may be swamped by the gain you get in converting. The second is that having a universal language in which any NP problem can be posed would be extremely useful for programmers and application development, and even if you take a performance hit the added flexibility and generality could be worth it.

Alright back to automatic programming. Let’s assume that we have a set of problem specifications making up the desired product specifications for a software product. Let’s further assume that all of these problems are no worse than NP-complete. Further assume that we can divide these problems into two categories: those in P, and those not in P. If we have a declarative language that allows us to program by specifying only what a solution looks like, with automatic conversion to some canonical solver language, then I think this is sufficient for automatic programming.

The reduction for P problems we already have (P problem stated in Java–>matrix multiplication for example). In this framework we’d need a high level declarative language for problems in P (declare the solution specs, and an automatic process converts to a canonical problem in P (like matrix multiplication), which is then solved by conventional hardware, probably specifically optimized for that problem).

I’m going to speculate that if we had a machine that could do the same automatic reduction with a general and flexible NP-complete solver, taken together with the P solver above we’d have an automatic programming system for nearly all human-related software engineering projects.

OK so I’m going to tentatively put automatic programming into the applications section. Specifically I’m going to assume the following:

1. A black box solver of two-dimensional Ising model in magnetic field (ISING), which was extremely fast and accurate, could be used as a solver for a high level declarative programming language for all problems that can be polynomially reduced to ISING.
2. The lack of a high-level declarative language that returns highly accurate solutions quickly even for extremely large NP-complete problems is the main barrier to automatic programming; all of the other knowledge and technology to solve this problem already exists.

It’s pretty clear that automatic programming meets the requirements for a good application–this one would definitely be over $1B/year in revenue.

I thought this was quite interesting. It’s the slides from the 1998 Turing lecture, given by Jim Gray talking about what enabling technologies would have the most value for IT. Remarkably prescient given the date of the talk and how fast things change.

Here is a particularly interesting screen grab from p.47:

Gray sees such a system “discussing” the system with the designer…and mentions that this is a type of Turing test–the automated programming system is imitating a programmer.

I wonder how close to this vision a good declarative language would be?

What I’m going to try to do is list a bunch of applications that require the solutions of NP-complete or NP-hard problems. These will be found under the Applications tab in the sidebar.

I’m going to try to restrict the list to applications that have the following properties:

1. Problems people really want to solve are too big for exact solvers
2. People are not happy with the level of approximate solutions they can obtain with the best known heuristics
3. The people in 1. and/or 2. would see significant value in being able to solve bigger problems, faster and would make or save a lot of money if this were possible; I’ll try to include only if customers might be willing to pay in excess of $1B/year for satisfactory solution of their problems

Note I’m not saying these problems ACTUALLY have $1B markets, I’m saying that it might be possible. If anyone out there in blogland has actual market numbers to any of these problems that would be very useful.

Any suggestions for problems like this would be greatly appreciated (existing apps or new ones, doesn’t matter); any info on desired customer solution characteristics (size, accuracy, speed, etc.) would be great also.

The protein folding problem is this: given the primary structure of a protein (its linear sequence of amino acids), compute its three dimensional shape. Here is a good introduction.

One approximation that is often made to simplify the problem is to restrict the aminos to a lattice. A further restriction is to label all aminos as either H (hydrophobic) or P (hydrophilic).

Restricting to a lattice and H & P aminos gives the HP model, invented by Ken Dill. Finding the global energy minimum of this model of protein folding is NP-complete.

The other day I got sent this, which details some of the core beliefs of scientology. Man this religion is awesome. Founded by a bad science fiction writer, the core belief is that some intergalactic dude named Xenu (no relation to Xena) stacked aliens around volcanoes on Earth 75 million years ago and then vapoorized them with hydrogen bombs.

For more information on this, possibly funniest religion ever, check out this link, if just to watch the South Park episode.

…is here. Great stuff.

One of the themes, which I totally agree with, is that quantum computation helps frame the whole “interpretations of quantum mechanics” boondoggle in a useful way. This topic was touched on also by Dave Bacon a few weeks ago.

Deutsch’s point of view, which I share, is that accepting quantum mechanics to be an objective description of reality logically implies the many-worlds picture.

This is the way I have always thought about quantum mechanics, and I certainly don’t have any problem, technical, philosophical or otherwise, with the objective reality of the variety of possible worlds. When we operate one of our machines, I always think of 2^16 (or however many qubits) universes, all with everything identical except the values of the 16 bits on the chip, all having objective reality. I am OK with the idea that my history most likely tracks through the universe with the correct answer if I set up my machine language correctly.

What I don’t get is why physicists, and specifically those that use quantum mechanics regularly, have a problem with the reality of the many-worlds implications of QM. It’s certainly the case that advances in science often reveal that things aren’t always what they seem, and that fundamental truths don’t have to be obvious. We are clearly extremely limited in our perceptive capabilities…why should we be confused or distressed if it turns out it’s hard for us to “pierce the veil” and see things as they are? And why should we be surprised if the true nature of things doesn’t always match our 5-sense grounded expectations?

I think I have found it. It is here.