I often ask for a "simple" algorithm that solves some problem and I realized that, almost aways, the answerers's notions of simplicity doesn't match mine's. Often, for example, I notice people using numbers inside a supposedly "simple" answer, ignoring the fact numbers are, themselves, a complex dependency which adds a ton of bytes to the implementation of that algorithm in any language that doesn't have arithmetics (addition, multiplication, division, modulus, etc.) as primitives. Maybe that is partly due to fact most human programming languages have numbers built in, but that is merely an accident due to our obsession with numbers.

When I ask for a "simple" algorithm, I mean one with low Kolmogorov Complexity. That is, I want something that is simple to implement on the average neutral language: it must be simple in Python, in C, in brainfuck or on the untyped lambda calculus. Its simplicity must be inherent, not depend on the specific language. Sadly, I can't ask specifically for that, because the Kolmogorov Complexity of an object is undecidable. Nether less, certain things are just obvious. For example, an implementation of XOR is certainly, inherently less complex than an implementation of SHA256, in any "neutral" language. But then, how could I define a "neutral" language? Those things make it very hard to ask formally for something that is simple, despite the meaning being so obvious to me. I could ask specifically for the size of the program on the binary lambda calculus, but on my experience that just shies people away from my question.

My question, is: how do I properly ask for a "simple" algorithm, given the above notion of simplicity?

  • $\begingroup$ Prove tight lower bounds for the circuit complexity of your problem and only accept algorithms that match the bounds? $\endgroup$ – adrianN Jan 26 '17 at 16:02
  • $\begingroup$ What is circuit complexity and how I prove things about it? $\endgroup$ – MaiaVictor Jan 26 '17 at 16:23
  • $\begingroup$ en.wikipedia.org/wiki/Circuit_complexity In general you don't prove things about it, the field has been mostly stuck for at least thirty years. $\endgroup$ – adrianN Jan 26 '17 at 16:25
  • $\begingroup$ Circuit complexity is a horrible notion as it is (i) very model-dependent, and (ii) non-uniform (unless you consider uniform circuits). $\endgroup$ – Yuval Filmus Jan 26 '17 at 17:49

Your Answer

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

Browse other questions tagged or ask your own question.