Does Program Size Matter?
A problem about this forgotten complexity measure
Erik Winfree is one of the leaders in DNA computation, especially the theory of self-assembly using DNA. He won a MacArthur Fellowship in 2000, among many other awards for his terrific work. With Paul Rothemund he wrote a STOC 2000 paper titled “The Program-Size Complexity of Self-Assembled Squares,” work that contributed to their sharing the 2006 Richard Feynman Prize in Nanotechnology.
Today Ken and I want to talk about program size: about how many instructions are needed to compute something.
A DNA self-assembly system consists of a set of tile types, rules of assembly, and theorems of the form:
The number of tile types to create is at most …
The rationale to reduce tile types is simple: making duplicates of tiles is like printing, its cheap; but making many types of tiles is expensive. Each tile type requires a separate printing. So there is a natural imperative to reduce the number of tile types.
Hence a major goal of their research, using their terminology, is to reduce the “program complexity.” Thus there are parts of computer science theory where program size is important, but this area uses a non-standard notion that may say nothing about programs for conventional computers, which are the kind we want to study.
If you are interested, consider going to the next DNA Conference which was started by one of us, Dick, years ago. They are now on the twenty-first edition.
Let’s look at program size of machines not tile systems, since it came up recently in some thoughts Ken and I had on . We do think about that question sometimes…
Size of Code, Old and New
In the real world the size of a program is probably much more important than the time it takes or the amount of memory it requires. The size of code directly correlates with the cost of writing the program and maintaining it, with its number of bugs, and with its security issues. Big program are usually expensive in all ways. If we are creating the next great app that will make us all a fortune, we want the program to be a manageable size.
Yet complexity theory—for the most part—is focused almost entirely on the time a program takes or the space it uses. Not on its size. Hence we study time classes like and space classes like , logspace. And we prove theorems like hierarchy theorems. But not many theorems say anything about the size of a program. In one of the first posts on this blog, I posed this challenge:
Prove there is no algorithm for that runs in polynomial-time and can be written down on a single piece of paper. You can make the paper 8.5 by 11, if you wish. The writing has to be normal size. No tricks.
I went on to say that while “conventional wisdom” is confident in , so that no such program exists, yet I find it shocking that even this one-page challenge appears to be hopeless.
Well perhaps we can prove it equivalent after all, in the course of raising two questions. The first is about program size overall, and the second about the size of “new code” that needs to be written to solve a new problem, versus using already-written routines. To further our-real-world analogy, the latter have presumably already been debugged, and no one has to pay for writing them again.
Let’s look at the main obstacle and then the two questions.
Here is the source of our questions that we have recently thought about. Imagine, try to imagine if you can, that . This implies that every nondeterministic Turing Machine (NTM) that runs in linear time can be simulated by a deterministic TM (DTM) that runs in time for some constant . The constant is absolute, but it can be small or large or astronomical. Thus one reason that could still imply nothing about practical computing is that could be the obstacle. Even a modest size would render many applications useless.
This is nothing new—we have pondered before that could be huge. And have postulated that one reason that none have found such a deterministic algorithm is that most tools in algorithm design are not set up to create algorithms that have running times of the form
Dynamic programming, divide-and-conquer, clever data structures, random sampling, linear programming, semi-definite programming, and others do not yield such galactic running times.
Ken and I wonder if the obstacle could be not that is large, but that the program size hidden away in the statement
has a blowup. Suppose that . That would sound great—too good to be true. But it could still be useless. What if given an NTM program that runs in linear time, the corresponding DTM program that runs in time is itself huge? The fact that the program is deterministic and runs fast is really of no value if the program is exponentially larger than . If this is the case, then even though the running time is small, the program is of no value.
This is the obstacle that we are interested in. Our response will involve universal simulators, which can be small, even tiny. We will first wrap one inside a famous old construction by Leonid Levin, and then write a little more “new code.” But first, what questions might a complexity theorist ask about program size?
Two Simple Questions
For both questions, our general task will be taking a nondeterministic program of size that runs in some nondeterministic time , and simulating it by a deterministic program of size in time that is at most polynomially slower: . It’s enough to suppose is linear, so the goal is . We won’t care if is huge, so long as it is fixed and avoids being huge. Our questions are:
- Could it be that any polynomial-time deterministic program must be exponentially bigger, that is ?
- Can we arrange that , or even , where the constant in the is not only independent of (of course), but also small in an absolute sense?
Of course if these questions are generally moot. But if , could the reason for the equality not being practical be that the program blows up in size, not that the running time blows up? Put another way, could we have but requires a program so large that it cannot ever be used? Note, this says nothing about the running time of the algorithm.
The short answer to the first question is no. This is because of reducibility and completeness for . The code for the reduction from the language of to is linear in the size of . Call this code . By there is a fixed deterministic polynomial-time program for . The program that takes an input and outputs runs in poly-time and has size . Moreover itself can be viewed as a fixed piece of code that takes the code of as a parameter, so the size can be regarded as or even just in terms of “new code.”
However, the ‘O’ here includes the unknown size of the possibly-huge program . Hence this doesn’t fully answer the second question. That’s our point: can we do better?
The basic idea, Levin’s “universal search,” is well known, and we covered one aspect of it here. We have not seen it addressed regarding program size, however.
Levin’s universal machine accepts a Boolean formula only when it has found a satisfying assignment. Call this “verified acceptance.” It means that can possibly err only by rejecting a that is satisfiable after all. If is true, then Levin’s code—which is known and small—will run in polynomial time, and accept except for finitely many errors.
What does on a formula of size is first spend steps trying to prove that the first yea-many small polynomial-time programs don’t recognize with verified acceptance. Let be the least program that does not fail this test. then runs . If it gives a satisfying assignment, accepts ; else rejects. Then the code has size with “new code” where the constant in the is small and known, not huge.
If , then some runs in polynomial time , and (by the self-reducibility of ) recognizes with verified acceptance. Let be least for this. Then each of the machines makes some mistake, and some finite time suffices for to cross off each one. Hence whenever , simulates and gives the same answer in basically the same time, which becomes the overall polynomial runtime of . This carries over to runtime for our code on of length .
The issue is, what happens when ? Our code may err. We could “patch” it by adjoining a lookup table for the finitely many errors. But this table becomes part of the program size and might be huge. Moreover a given table could be buggy—remember that the famous Pentium bug of 20 years ago came from a few bad lookup-table entries.
Levin originally stated his for factoring rather than . The point is that the language
belongs to , and so can be recognized with verified rejection as well as verified acceptance. Then with reference to the above description of in general, rejects only if outputs a verified rejection. If gives no verified answer, then takes as much time as it needs to get the correct answer. This still settles down to polynomial time for .
Thus it is not possible to have factoring in but all polynomial-time programs for it are huge. To be sure, the running time can be huge—indeed itself may be huge and its size gets reflected in concrete running times—but the code for itself is small. And it is all known code which can be already debugged.
We could try to do the same for by having solve exhaustively if fails to find a satisfying assignment. The problem then becomes not knowing when to stop and “trust” when in fact the first good one is found. The nub is whether we can use the assumption of to “bootstrap” the verification of succinct proofs of unsatisfiability. The mere existence of succinct proofs, however, that are verifiable without the assumption implies .
Can we make the short code simulating perfect, without patches? We like the metaphor of as interacting and adapting in an environment of short programs, which it “assembles” into its own code before finding the one that works best.
We are not bothered about the conversion time being exponential in the size of the that is ultimately selected. After all, compared to the short timespan of recorded human history, the time it has taken us to evolve feels “exponential.”
Can we write code today, on one sheet of paper, that accepts exactly and runs in deterministic polynomial time if ?
Incidentally Ken fit much of a 3-tape Turing machine that does universal simulation of assembly programs onto one sheet for Buffalo’s theory courses.