4 ms·

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

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

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.

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