Hacker News Reader

Comment by crimsonalucard | Hacker News Reader

>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?

View on HN

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 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 )

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

Reply on news.ycombinator.com