What problem cannot be solved by a short program?

Question

BACKGROUND:

Recently I tried to solve a certain difficult problem that gets as input an array of $n$ numbers. For $n=3$, the only solution I could find was to have a different treatment for each of the $n!=6$ orderings of the 3 numbers. I.e., there is one solution for the case $A>B>C$, another solution for $A>C>B$, etc. (the case $A>C=B$ can be solved by any one of these two solutions).

Thinking of the case $n=4$, it seems that the only way is, again, to consider all $n!=24$ different orderings and develop a different solution for each case. While the solution in each particular case is fast, the program itself would be very large. So the runtime complexity of the problem is small, but the "development time" complexity or the "program size" complexity is very large.

This prompted me to try and prove that my problem cannot be solved by a short program. So I looked for references for similar proofs.

The first concept that I found is Kolmogorov complexity; however, the information I found about this topic is very general and includes mostly existence results.

QUESTION:

Can you describe a specific, real-life problem $P$, such that any program solving $P$ on an input array of size $n$ must have a size of at least $\Omega(f(n))$, where $f(n)$ is some increasing function of $n$?

Since the answer obviously depends on the selection of programming language, assume that we program in Java, or in a Turing machine - whichever is more comfortable for you.

Every undecidable problem trivially satisfies this requirement because it has no solution at all. So I am looking for a decidable language.

Answer 1

I assume that what you actually want is an enumeration of problems such that the corresponding programs form an increasing sequence in size. Here is an exemple of such an enumeration. However, I only prove that the size increases beyond any bound, hence it is not in $O(1)$, which seemed to be your main point. I could try better, but I am wondering what in this answer might not be acceptable in your view of the question.

If I understand correctly, you want an enumeration $P_n$ of problems that are all decidable with an algorithm $A_n$, such that there is no uniform decision procedure for the union of these problems, because if there was one, it would be a short program when $n$ gets large, i.e. it would be $O(1(n))$.

That implies that the enumeration $A_n$ is not computable. If it were computable, the one would be able to compute the algorithm $A_n$ from the knowledge of $n$, thus having a uniform procedure for the union of all the problems in the enumeration.

Hence we can only look for examples such that there is no computable enumeration $A_n$ of algorithms such that $A_n$ solves $P_n$.

Before going into that, we need to define the size of a

Let $T_n$ be a enumeration by Gödel numbers $n$ of Turing Machines. Such a Gödel enumeration is computable. Then let $P_n$ be the following problem: if $T_n$ halts on all inputs, then $P_n$ consists in recognizing the recursive set recognized by $T_n$, else $P_n$ consists in recognizing the empty set $\emptyset$.

Since we are looking for lower bounds on the size of the algorithm $A_n$ that solves $P_n$, we have to define the size of a TM. For a TM, its Gödel number can be taken as the size of the machine, i.e. the corresponding algorithm. Indeed the number of states and transitions increases necessarly with $n$, if only because of the pigeon hole principle, though it is not necessarily uniform (and it depends on an arbitrary definition of size anyway).

Then, for any TM $T_n$ that always halt, we note ${\mu(n)}$ the smallest Gôdel number of a TM $T_{\mu(n)}$ such that it always halt and recognizes the same recursive set as $T_n$. Hence $T_{\mu(n)}$ is the smallest TM that actually is an algorithms to solve $P_n$, i.e. it is $A_n$. If $T_n$ may not halt, then for $A_n$ we simply use always an algorithm corresponding to a TM $T_\emptyset$ the recognizes the set $\emptyset$, always the same one.

Each problem $P_n$ is decidable, and $A_n$ is a decision procedure. However, the enumeration $A_n$ is not computable, but we have shown that it is unavoidable.

It is easy to show that, given any constant $C$, there is an $n$ such that the size $|A_n|$ of $A_n$ is greater than $C$. The reason is simply that the number of machines smaller than $C$ is finite, while the number of recursive sets recognized by TMs is infinite.

So that is an example of a problem (more precisely a problem enumeration) that cannot be solved by a short program, i.e. such that there is no constant bound on the length of solutions for each $P_n$.

We can always add to each problem $P_n$ that it requires any solution to first read an array of size $n$, so as to meet the constraint in the question. But there is little point to it.

Answer 2

For any given problem, you can create a programming language where a program to encode the solution to that problem is a single character. (cf. HQ9+). Kolmogorov complexity is language dependent. The answer to your question about which problems cause a blowup will depend heavily upon whichever "standard formal language" you choose.

There are some interesting results, however. Encoding of randomly generated strings will always require a cost proportional to the size of the string. Pigeonhole principle tells us there will always be some functions, in any fixed language L, that cannot be expressed in a space smaller than a complete enumeration of all the cases. And Blum's size theorem tells us that, for a total language, there are always functions you can encode larger than an arbitrarily chosen blowup factor compared encoding the same function in a Turing complete language.

Answer 3

A result of Shannon's states that there exists a sequence of functions $f_n\colon\{0,1\}^n\rightarrow \{0,1\}$ that is so that the problem $P(n)$ of computing $f_n(x)$ for $x\in\{0,1\}^n$ requires at least $\Theta(\frac{2^n}{n})$ boolean operations (i.e. the circuit complexity of computing $f_n(x)$ is at least $\Theta(\frac{2^n}{n})$).

This theorem is not so hard to obtain, as there are $2^{(2^n)}$ $n$-ary boolean functions, while the number of circuits of the given size is strictly smaller.