4 ms·

>A solution can not be simpler than the problem. Problem: (4 primitives) 1 + 1 + 1 + 1 Solution (one primitive): 4 If amount of primitives defines comp

>A solution can not be simpler than the problem. Problem: (4 primitives) 1 + 1 + 1 + 1 Solution (one primitive): 4 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?

jessermeyer 7y ago
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.
- crimsonalucard 7y ago
  https://news.ycombinator.com/item?id=22378553 https://news.ycombinator.com/item?id=22378553
BoiledCabbage 7y ago
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.
- crimsonalucard 7y ago
  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: 4 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.
  - BoiledCabbage 7y ago
    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.
    - 7y ago
carapace 7y ago
> 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 http://pespmc1.vub.ac.be/ASHBBOOK.html )

jessermeyer 7y ago

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.

crimsonalucard 7y ago
https://news.ycombinator.com/item?id=22378553 https://news.ycombinator.com/item?id=22378553

BoiledCabbage 7y ago

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.

crimsonalucard 7y ago
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: 4 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.
- BoiledCabbage 7y ago
  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.
  - 7y ago

carapace 7y ago

> 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 http://pespmc1.vub.ac.be/ASHBBOOK.html )