debugMinor
What problem cannot be solved by a short program?
Viewed 0 times
cannotproblemwhatshortprogramsolved
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#32114, answer score: 7
Revisions (0)
No revisions yet.