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

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