1
$\begingroup$

I am interested in the relation between "program complexity" and "computational complexity".

In particular, I was wondering

What is known about the minimal length a program must have to solve a given problem (efficiently)?

Is there such thing as "program complexity-bounded" computational complexity classes?

Any information related to the topic is much appreciated. Is this an active research area? What are open problems? References to textbooks, research articles? etc.

(Googling this, all I find is "resource-bounded Kolmogorov complexity" etc., but that seems to be the exact opposite of what I am looking for...)

EDIT: Some context: In the field I am working in the argument "simple algorithms cannot possibly perform as good as complex ones", is often quoted to motivate unnecessarily complex approaches. While this is by itself an insufficient argument, I can understand that some problems indeed might require a minimal complexity to be solved (efficiently?). However, I was wondering whether there were any general theoretical results supporting this notion, or research being performed in this direction.

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ In what way is resource-bounded Kolmogorov complexity the opposite of what you want? It seems like a pretty good answer to your question in bold. Or do you mean to ask what is known about the resources needed (time, space, etc) to solve a given problem given constraints on the program size? $\endgroup$ – Joshua Grochow Mar 15 '18 at 19:21
  • $\begingroup$ I imagine that you could define something like Kolmogorov complexity for Languages: the kinda-K-complexity of a language is the shortest description length for a machine that decides (or maybe recognizes) your language. I have no idea whether something like this has been studied though. $\endgroup$ – Mikhail Rudoy Mar 16 '18 at 1:29
  • $\begingroup$ This seems to be what OP wants. In his opening statement, he says that he wants to establish a relation between "program complexity" and computational complexity and thinking about it, I could imagine that one indeed can prove that certain languages need "large programs" in the sense that a TM deciding them needs many states. In fact, the Myhill-Nerode theorem could be seen as such a result. Also, every infinite complexity class must contain languages of arbitrarily large "program complexity" if we use the Kolmogorov (or state) metric. $\endgroup$ – Watercrystal Mar 16 '18 at 1:45
  • $\begingroup$ @Joshua Grochow: "Or do you mean to ask what is known about the resources needed (time, space, etc) to solve a given problem given constraints on the program size" => this is exactly what I want. (not sure why this got downvoted, is my question unclear?) I edited my question to provide some context. $\endgroup$ – Codiloo Mar 16 '18 at 14:11
  • $\begingroup$ @Watercrystal: "every infinite complexity class must contain languages of arbitrarily large "program complexity" if we use the Kolmogorov (or state) metric". This sounds interesting. Perhaps worth elaborating on and posting as an answer? $\endgroup$ – Codiloo Mar 16 '18 at 14:38
4
$\begingroup$

Elaborating on my comment as suggested by OP:

Let us start by giving definitions to the two definitions for program complexity as suggested by the other commenters and me.

Definition (Kolmogorov complexity of $L$): Let $L$ be some language. We define the Kolmogorov complexity $K(L)$ of $L$ to be the (description) length of the smallest program which decides $L$ (using some fixed programming language) or $\infty$ if no such program exists.

Definition (State complexity of $L$): Let $L$ be some language. We define the state complexity $S(L)$ of $L$ to be the minimal number of states a TM which decides $L$ needs to have or $\infty$ if no such TM exists.

The first observation we make is that there are only finitely many programs of length $n$ (and the same holds for Turing machines if we fix the alphabets and state names). It follows that any infinite class $\mathcal C$ of languages and any $m \in \mathbb N$, there is some language in $\mathcal C$ which has a Kolmorogov complexity which is at least $m$ (and the same holds for state complexity).

Indeed, this means that even problems which can be decided in constant time can have an arbitrarily large program complexity, which makes me pessimistic about the existence of results that imply that a large program complexity incurs a large runtime complexity. What about the converse statement?

The same argument from above yields directly that if we have two (infinite) decidable complexity classes $\mathcal{C}_1$ and $\mathcal{C}_2$, then for any $L_1 \in \mathcal{C}_1$ there must exist some $L_2 \in \mathcal{C}_2$ with $K(L_2) > K(L_1)$ (and the same result holds for state complexity) as $K(L_1)$ is finite (by decidability) and he program complexity for any infinite complexity class is unbounded. Even stronger, it follows that there exist infinitely many such $L_2$ and the difference in program complexity can be arbitrarily large (again by the first observation). In particular, one can deduce that for any decidable language, there exist infinitely many languages with (arbitrarily) larger program complexity but constant time complexity.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for elaborating. So one could basically state the following: $\endgroup$ – Codiloo Mar 17 '18 at 17:20
  • $\begingroup$ Any bound on "program complexity" (Kolmogorov or states) necessarily shrinks any infinite complexity class? For instance, for any finite $m$, there are (infinitely many) problems in $P$ which cannot be decided in polynomial time by a deterministic TM having less than $m$ states. (sorry for the double comment, posted it by accident and edit timed out...) $\endgroup$ – Codiloo Mar 17 '18 at 17:34
  • $\begingroup$ Yes, this is a direct implication of the fact that $\mathsf P$ is infinite, but the number of Turing machines with at most $m$ states is finite. $\endgroup$ – Watercrystal Mar 17 '18 at 17:53
0
$\begingroup$

What is known about the minimal length a program must have to solve a given problem (efficiently)?

** In some ways **, the minimal length matches the minimal length of an efficient Universal Turing machine $U$ that treats its input as a pair $\langle M, x \rangle$ in some fixed encoding (e.g. $1^{|M|}0Mx$), and simulates $M$ on input $x$.

Indeed given a language $L \in \mathcal{C}$ decided by $M$ you can simply transform an input $x$ in $1^{|M|}0Mx$ and use $U$ to compute $M(x)$. In other words, whatever language you pick there is a linear time reduction that you can use in combination with the tiny $U$ to solve the problem.

Or another way to see it is: given a problem, there is an equivalent problem in which the input representation is a little bit less efficient, but for which the minimal program that solves it is $U$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ If I understand you correctly, you argued that "every problem can be (efficiently) reduced to a problem which can be solved by a short program ($U$)." However, I feel one cannot ignore the complexity (description length) of this linear time reduction itself (as in essence not U but U+reduction solve the original problem). Surely, the minimal length of this reduction depends in general on $|M|$? Or do I see this wrong? $\endgroup$ – Codiloo Mar 17 '18 at 17:00
  • $\begingroup$ No, your observations are correct. Mine is only a simple observation (trivial according to the downvotes :-D) that if you're focused only on the program length, then you can "hide" the minimum TM that solves a problem in the input (with a minimum overhead) and use (efficiently) a tiny Universal machine. In other words ... what happens if you have only a bunch of bits to code a program? ... nothing, use them to code a Universal TM and you can still efficiently do any computation. $\endgroup$ – Marzio De Biasi Mar 17 '18 at 19:27

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.