Hacker News Reader

Comment by jerf | Hacker News Reader

Complexity is not conserved. It is a bound. A solution can not be simpler than the problem, when both are viewed holistically and complexity is properly understood. (Yeah, I'm handwaving, but at least I acknowledge it. I don't want to write twelve paragraphs defining "complexity" right now, because my real point is....)

But the solution sure can be more complicated than the problem.

View on HN

That is more or less what TFA says: "Every application has an inherent amount of irreducible complexity." "Irreducible" means a bound, but it does not mean a constant.

The name is misleading to a scientist, who has a specific understanding of what "conservation" means. And in particular, a very specific notion of what a "conservation law" is. Which this does not follow.

Getting past the name, it's a useful adage. But the name adds unneeded complexity, placing a burden on people who are forced to learn a different intention for a well-understood term.

If the complexity is truly irreducible, is it possible to truly hide it from the user either?

Continuing to handwave, if the system as a whole is something like "user complexity + program complexity >= problem complexity", you can indeed hide it from the user in many cases by pulling it into the program itself. Otherwise, programs would have no utility at all. That's essentially their whole purpose, is to pull it away from the user by putting it in the program.

Probably not, but you are pointing out kind of an oddity in the adage. Complexity should always live on the side of the developer, not the user. Any design choice that says, "We could figure out how to do this, but we didn't, so we'll make the user do it for us" is just outright bad. That's not an adage; that's just an injunction not to be a bad designer.

What's more interesting is that even within the domain of the user space, there is an irreducible complexity. You can push it around, but you can't make it go away. Figuring which users you will inconvenience, how often, and how bad it will be -- that's the artistry.

You can replace a hard disk with a solid state drive, and most users would not notice a thing except it might be a bit faster and less noisy. An enormous amount of complexity is hidden behind a simple interface.

Fred Brooks wrote a book about complexity, accidental and essential. Essential complexity is the lower bound to which you refer, and the hard limit that prevents major advances in programmer productivity.

https://en.wikipedia.org/wiki/No_Silver_Bullet

>A solution can not be simpler than the problem.

Problem: (4 primitives)

  1 + 1 + 1 + 1

Solution (one primitive):

If amount of primitives defines complexity you are wrong.

What's going on here is that you are using a different definition of complexity to construct your statement above. Most humans intuitively recognize your statement along with mine.

The issue here is that before we can even talk about complexity we have to come up with a formal definition that fits all forms of our intuition about what complexity actually is. Otherwise all arguments can become circular and pointless as everyone is talking about different things.

What is the formal definition of complexity? What is the thing that is being preserved here?

I disagree with the above.

If you're listing 1 + 1 + 1 + 1 as 4 primitives (I think it's actually more once you include the primitive of addition), I don't think that 4 is the solution. The solution is a written up program that works on any integer that when run this particular sequence produces the value 4. And that solution/program is significantly more complex than 1+1+1+1.

Or alternatively if you say the program can't run on any other values, just that specific one so you can hardcode the result of the program to be "4", then I'd argue there initially aren't 4 primitives. there is one single primitive the entire entity "1+1+1+1" which is equivalent in inherent complexity to the primitive "4". Regardless of how complex we choose to represent it (ie with more characters or fewer), conceptually it's a single "primite" value input and it produces a single primitive value output.

This another definition issue. Traditionally a solution is defined as that expression reduced to the simplest possible form. Your definition of solution is more describing the process of reduction.

How about this. The problem is:

Create a solution that is equivalent in value but has 7 primitives. (Using your definition of "primitive" to include operators).

  1 + 1 + 1 + 1

Under both definitions of "solution" and under my example definition of "complexity" the statement that the solution cannot be simpler than the problem does not hold.

Problems like find every permutation of a string "abcdefg" has solutions more complex than the problem. Disregarding definitions I believe your intuition is a bit off here.

I agree it's a definition issue, but I believe it's your intuition that's steering you wrong. You're using a mathematical definition for a non-math domained problem. The domain of discussion is software. The quote from the article is:

Every application has an inherent amount of irreducible complexity. The only question is: Who will have to deal with it—the user, the application developer, or the platform developer?

In this case, I believe it's clear that the "problem" are the provided requirements of the software, and the "solution" is the union of the user's required knowledge, the application complexity and the relevant complexity of platform the app is running.

In this domain, "4" is not a well formed problem. Produce a program that when given "4" returns "4" is well formed. Produce a program that when given any integers and arithmetic primitives produces a reduced value is well formed.

And in both cases the solution/program to produce that is at minimum equally complex as the requirements description (if it were rigorously defined).

Or put in mathematical terms, the proof of a theorem/statement cannot be any less complex than the theorem/statement itself. The closest you can get is a trivial theorem/statement whose proof is of equal complexity to itself.

And back to the original post, it is handwavingly saying that every proof has some level of irreducible complexity. It is either captured in the complexity of poof itself, the complexity of the proof system / axiomatic-system being used or (here is were the analogy breaks down a bit) in the required user's knowledge.

>Or put in mathematical terms, the proof of a theorem/statement cannot be any less complex than the theorem/statement itself. The closest you can get is a trivial theorem/statement whose proof is of equal complexity to itself.

I don't think this analogy is apt. The domain of all problems and all associated solutions which programming covers includes proving theorems but this does not fill the entire set of all problem and solution pairs.

A problem could be: given axiom A and axiom B what are 100 theorems that you could generate that utilizes one axiom or the other or both? This is analogous to my reversal of the addition problem. The solution is not deterministic and is not irreducible.

In your vernacular you use the term well-formed without fully defining it. Intuitively I think by well-formed you mean deterministic and irreducible.

The domain of all problems and solutions includes "well formed" as a subset but encompasses much more than that. Programming is able to generate "1 + 1 + 1 + 1" from 4 and simply because it is 100% possible to write a program that does this, therefore the context of the discussion includes problems and solutions that are not well formed.

Your intuition is wrong in the sense that you believe all problems and solutions have to be "well-formed." They do not.

What you call the problem is actually the specification of the solution, which is the point. What you call the solution is another representation of the solution, but lacks the specification, so you _cannot_ use it to show that it _is_ a solution.

https://news.ycombinator.com/item?id=22378553

> What is the formal definition of complexity?

In re: that question I found "Introduction to Cybernetics" by Ashby to be very stimulating. (PDF freely available from here: http://pespmc1.vub.ac.be/ASHBBOOK.html )

Isn't that the distinction between accidental and essential complexity? A solution cannot be simpler than the essential complexity of the problem, but it can surely be more complex by adding accidental complexity.

This is kind of a word game though. As soon as you find a way to lower complexity it becomes the new essential complexity until someone lowers it again.

Are you arguing there is no such thing as essential complexity? In that case it would be possible to compress any program down to one bit, without moving the complexity elsewhere.

The solution can sometimes be simpler than the problem, if the problem is redefined so that it isn't as complex. Quite often this is the case when tunnel-visioned on a particular process and focusing on how to do that thing. Stepping back and thinking about why or what the end goal actually is, and then doing something else, is often the only real way to meaningfully reduce complexity.

Doesn't P=NP say otherwise? Given the solution, the problem becomes polynomial time to verify. Hindsight 2020

I think the comment was a little tongue-in-cheek -- like FizzBuzz is a problem without much inherent complexity, but you can certainly you make an overly complex solution: https://github.com/EnterpriseQualityCoding/FizzBuzzEnterpris...

Reply on news.ycombinator.com