7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "specific algorithmic" $\: \mapsto \:$ "specific sequence of algorithmic" $\;\;\;$ ? $\;\;\;\;\;\;\;$ $\endgroup$ – user12859 Oct 20 '14 at 7:31
  • $\begingroup$ Can you be more explicit regarding your last sentence regarding trivial answer with any undecidable problem. I have one interpretation of it, but I do not find it convincing. $\endgroup$ – babou Oct 20 '14 at 12:14
  • $\begingroup$ Do you have to start again looking for a solution for each value of n, reasonning from scratch? Or is there a method to arrive at the right program, when n is known? I do not understand what you mean by development time complexity ... does it depend on your ingenuity? $\endgroup$ – babou Oct 20 '14 at 13:02
  • $\begingroup$ @babou: If a problem $P$ is undecidable, then there is no program solving $P$. Therefore, anything you say about "any program solving $P$" is true because there is nothing to contradict it. Everything you say about the elements of an empty set, is trivially true. $\endgroup$ – Erel Segal-Halevi Oct 21 '14 at 7:04
  • $\begingroup$ @babou: I mean that for each value of $n$ you have to think about a solution from scratch. $\endgroup$ – Erel Segal-Halevi Oct 21 '14 at 7:29
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. This indeed answers the question. What I am really looking for (but don't know how to ask correctly) is a natural problem, a problem that occurs in real-life, where the size of the program increases with the size of the input. $\endgroup$ – Erel Segal-Halevi Oct 23 '14 at 7:10
  • $\begingroup$ @ErelSegalHale I was aware of this real life aspect, but I am not sure what would distinguish it from a TM answer, given the peculiar properties of the problem, such as non the non-computable enumerability of solutions. If your problem enumeration is natural, I was actually wondering how you can prove that they are all decidable, unless they were constructed to be so. Undecidability is usually proved (ultimately) by contradiction, but decidability is usually proved constructively, which amounts to giving the decision procedure for all, which you cannot do as they are not computably enumerable. $\endgroup$ – babou Oct 23 '14 at 9:23
  • $\begingroup$ "I am not sure what would distinguish it from a TM answer, given the... non-computable enumerability of solutions" - This is a good point, thanks. $\endgroup$ – Erel Segal-Halevi Oct 24 '14 at 6:58
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "∃ functions, in any fixed language L, that cannot be expressed in a space smaller than a complete enumeration of all the cases." What is all the cases? Do you have a reference on the web? $\endgroup$ – babou Oct 20 '14 at 22:18
  • $\begingroup$ I mean a complete enumeration of (domain,range) pairs. You can construct such functions, e.g. mapping from a fixed set of random strings to another fixed set of random strings. Sorry, I don't have a reference to point at. $\endgroup$ – dmbarbour Oct 21 '14 at 2:28
  • $\begingroup$ I guess you mean an enumeration $P_n$ of such problems so that each $P_n$ has to be as large as the enumeration of the n (domain,range) pairs (Is that correct?). Too bad you have no clue for finding more information about this. $\endgroup$ – babou Oct 21 '14 at 8:19
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ OK, this shows the existence of a problem which requires a large program, but I am looking for a specific proof that a certain (known) problem requires a large program. $\endgroup$ – Erel Segal-Halevi Oct 20 '14 at 10:11
  • 1
    $\begingroup$ I knew that this was not a really satisfactory answer. I think that circuit complexity is the thing that is closest to "program length", as the size of the circuit varies with the size of the input, as in your post. Lower bounds in this area should be known for some specific problems, but I am not an expert. $\endgroup$ – zarathustra Oct 20 '14 at 12:10
  • 1
    $\begingroup$ I would think that the size of a circuit is more like the complexity of program execution rather than the size of program code. My idea is that each gate gets used only once. It is a kind of linear logic. If you do the same in software, where you can factorize by calling subprograms many times, do you have the same result on program size? CC @ErelSegalHalevi $\endgroup$ – babou Oct 20 '14 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.