20 ms·

In a certain sense complexity CAN be destroyed. Yes there is a minimal level of complexity that must exist, but given an entity with a purpose, in many cases it

In a certain sense complexity CAN be destroyed. Yes there is a minimal level of complexity that must exist, but given an entity with a purpose, in many cases it is possible to reduce the complexity of that entity without changing its' purpose. Take for example this function which adds one to an integer: function addOne(x: int) -> int { return (x * 1) + 0 - x + x + 1; } can be reduced to: function addOne(x: int) -> int { return x + 1; } The examples are obvious but from the examples you can deduce that their are many instances in software engineering where such reductions can exist but are not obvious at all.

jerf 6y ago
I phrase it as "The solution can be as simple as the problem but no simpler", which means, you can "create" complexity. We see this all the time in code, after all, we must account for this. But you can't make the solution simpler than the problem. There's kind of a "by definition" aspect to this, so it's kinda circular, but it's still a valuable observation, because we also see this in code all the time. For instance, it plays a significant role in the leakiness of abstractions; that leakiness is typically the attempt to make a solution that is simpler than the entire problem space. You can be fine as long as your particular problem fits in the space of the leaky solutions, but once your problem pokes out of that you can be in big trouble.
- davidw 6y ago
  Yes! > you can "create" complexity AKA "the complicator's gloves" https://thedailywtf.com/articles/The_Complicator_0x27_s_Gloves https://thedailywtf.com/articles/The_Complicator_0x27_s_Glov...
- crimsonalucard 6y ago
  It's not that simple. For one we don't have a formal definition of "simple" and secondly, even when we do have a definition of "simple" for certain contexts, we can never prove that something is at its' "simplest" state or not at its' "simplest" state. For example, newtons laws of motion, seemingly is a simple solution to finding a formal method of describing motion. It seems to fit the problem but there is no way to verify that it is the simplest solution to the problem and we don't even really know what "simple" is. We know through experimentation that relativity fits observations more accurately but even with relativity we don't know if it's the most "simple" solution or even if its' fully correct. Because you cannot know or ever know whether a solution is at its' simplest form, there is ALWAYS an opportunity for a reduction to be discovered. You absolutely cannot say that "The solution can be as simple as the problem but no simpler" because we don't know what "simple" is and we don't know whether or not a "simpler" solution may be discovered in the future.
  - llimllib 6y ago
    Just because it lacks a formal definition does not mean that somebody cannot say it. It's a human notion, not a formal one. (Also: I'd suggest that it's pretty rude to tell somebody they "absolutely cannot say" something, and try to avoid telling you that you absolutely cannot say that somebody absolutely cannot say something)
    - crimsonalucard 6y ago
      Human notions and formal notions overlap. All formal notions are human because they are developed by humans but not all human notions are formal because formal implies internal consistency and not all humans are rational. The difference between the two sets: Human intuition and Formal notions is the set of all notions that are contradictory or irrational. Humans can be contradictory or irrational but we should try to avoid it. >(Also: I'd suggest that it's pretty rude to tell somebody they "absolutely cannot say" something, and try to avoid telling you that you absolutely cannot say that somebody absolutely cannot say something) Maybe a better way to put it is: "Absolutely logically impossible' rather than "you absolutely cannot say." No offense intended.
  - mannykannot 6y ago
    There are formal definitions of complexity, of which Kolmogorov complexity is perhaps the best known. This may not be the sort of complexity you are thinking of (perhaps you have in mind 'hard to understand', which is an important issue that is not necessarily captured by formal measures), and formal metrics measure solutions, not problems (or, at best, a specific expression of a problem.) We cannot often decide whether a given solution is the simplest possible, but there are several fallacies that do not follow from this fact, such as: 1) Therefore, there cannot be a simplest solution. 2) Therefore, there is ALWAYS an opportunity for a reduction to be discovered. [1] https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity
    - crimsonalucard 6y ago
      >1) Therefore, there cannot be a simplest solution. I never said this, I said that you cannot verify that the current solution you have is the simplest solution. This is based off of science, nothing can be verified science. Because we treat software more as black box experiments rather than formal systems, verification of your solution as the simplest solution is impossible until you define formal axiomatic rules. But again, this is basically never done and Even than you'd have to deal with Godels incompleteness. >2) Therefore, there is ALWAYS an opportunity for a reduction to be discovered. There is always opportunity in the sense of "possibility" if a solution hasn't been formally verified to be its' simplest. 2 follows from the notion that complexity cannot be verified. > [1] https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity From your wikipedia source: "The notion of Kolmogorov complexity can be used to state and prove impossibility results akin to Cantor's diagonal argument, Gödel's incompleteness theorem, and Turing's halting problem. In particular, no program P computing a lower bound for each text's Kolmogorov complexity can return a value essentially larger than P's own length (see section § Chaitin's incompleteness theorem); hence no single program can compute the exact Kolmogorov complexity for infinitely many texts." The above states that the exact Kolmogorov complexity can never be computed for all texts and that this fact has been formally verified axiomatically. Doesn't this support my overall point? If you can't verify the complexity of a piece of text than you can't verify if it's the least complex because you don't even know the complexity let alone whether its' the least complex.
- aspenmayer 6y ago
  I would rephrase this as “the solution can be as simple as your model of the problem but no simpler.” A better model, structure, implementation, or restatement of the problem could transform the dimensions of the problem space radically. But I do agree with you in spirit of what you said, that there is some essential “hardness” of the problem that is part-and-parcel with the difficulty in stating or explaining the problem. I see a similar complexity in representing the problem in code or functions or algorithms etc. Then comes a related issue with reducibility; some concepts or problems cannot be broken down into smaller discrete parts. They are already as simple as they can be. This is ideal in a certain sense, in that the concepts can be explored with fewer assumptions. However when someone asks you to explain like they’re 5 years old, interpretation and perception starts to creep in through intuitions and abstractions.
- zmmmmm 6y ago
  > I phrase it as "The solution can be as simple as the problem but no simpler" Even that can be deceptive. For example, I can state very simply: I want to move my house 3 inches to the left It's a very simple problem right? How complex do you think the minimally simple viable solution is? It's about how the problem maps onto the constraints of implementation.
  - artfish 6y ago
    I am certain this is some kind of fallacy, since "house" is an abstraction that would need to be broken down somehow. The result would not be a simple problem anymore. Sorry, no fancy words, just common sense.
spacedcowboy 6y ago
I take your point, but the complexity I’m talking about is what remains after you’ve done any readily applicable simplifications. Any normal task has an inherent level of complexity (“add one” is a very simple task, so can be reduced down as you point out). “Invert a matrix” is somewhat less reducible. “Calculate a quaternion” even less so, etc. We generally string dozens or hundreds of these simpler tasks into sequences to get what we want, and human understanding being what it is, there’s quite a difference in conceptual complexity between “fly the plane to [here]” and doing all that maths. There’s probably a relationship to subitising here as well, the brain does seem to be able to process small groups of things, even if it knows those things represent larger concepts, better than larger groups of things. This is just speculation on my part though.
- crimsonalucard 6y ago
  I got into a really deep conversation about this here: https://news.ycombinator.com/item?id=23042796 https://news.ycombinator.com/item?id=23042796 You may have seen it, it's in the same thread of conversation we're having. Basically there's actually axiomatic proof that you can never know if you applied all possible applicable simplifications. Therefore you can never know whether or not more complexity can be destroyed or reduced.
jes 6y ago
With respect, I’m not seeing how your first addOne example returns an integer one greater than its integer argument. Am I missing something?
- crimsonalucard 6y ago
  (x * 1) + 0 - x + x + 1 x + 0 - x + x + 1 x - x + x + 1 0 + x + 1 x + 1

jerf 6y ago

I phrase it as "The solution can be as simple as the problem but no simpler", which means, you can "create" complexity. We see this all the time in code, after all, we must account for this. But you can't make the solution simpler than the problem. There's kind of a "by definition" aspect to this, so it's kinda circular, but it's still a valuable observation, because we also see this in code all the time. For instance, it plays a significant role in the leakiness of abstractions; that leakiness is typically the attempt to make a solution that is simpler than the entire problem space. You can be fine as long as your particular problem fits in the space of the leaky solutions, but once your problem pokes out of that you can be in big trouble.

davidw 6y ago
Yes! > you can "create" complexity AKA "the complicator's gloves" https://thedailywtf.com/articles/The_Complicator_0x27_s_Gloves https://thedailywtf.com/articles/The_Complicator_0x27_s_Glov...
crimsonalucard 6y ago
It's not that simple. For one we don't have a formal definition of "simple" and secondly, even when we do have a definition of "simple" for certain contexts, we can never prove that something is at its' "simplest" state or not at its' "simplest" state. For example, newtons laws of motion, seemingly is a simple solution to finding a formal method of describing motion. It seems to fit the problem but there is no way to verify that it is the simplest solution to the problem and we don't even really know what "simple" is. We know through experimentation that relativity fits observations more accurately but even with relativity we don't know if it's the most "simple" solution or even if its' fully correct. Because you cannot know or ever know whether a solution is at its' simplest form, there is ALWAYS an opportunity for a reduction to be discovered. You absolutely cannot say that "The solution can be as simple as the problem but no simpler" because we don't know what "simple" is and we don't know whether or not a "simpler" solution may be discovered in the future.
- llimllib 6y ago
  Just because it lacks a formal definition does not mean that somebody cannot say it. It's a human notion, not a formal one. (Also: I'd suggest that it's pretty rude to tell somebody they "absolutely cannot say" something, and try to avoid telling you that you absolutely cannot say that somebody absolutely cannot say something)
  - crimsonalucard 6y ago
    Human notions and formal notions overlap. All formal notions are human because they are developed by humans but not all human notions are formal because formal implies internal consistency and not all humans are rational. The difference between the two sets: Human intuition and Formal notions is the set of all notions that are contradictory or irrational. Humans can be contradictory or irrational but we should try to avoid it. >(Also: I'd suggest that it's pretty rude to tell somebody they "absolutely cannot say" something, and try to avoid telling you that you absolutely cannot say that somebody absolutely cannot say something) Maybe a better way to put it is: "Absolutely logically impossible' rather than "you absolutely cannot say." No offense intended.
- mannykannot 6y ago
  There are formal definitions of complexity, of which Kolmogorov complexity is perhaps the best known. This may not be the sort of complexity you are thinking of (perhaps you have in mind 'hard to understand', which is an important issue that is not necessarily captured by formal measures), and formal metrics measure solutions, not problems (or, at best, a specific expression of a problem.) We cannot often decide whether a given solution is the simplest possible, but there are several fallacies that do not follow from this fact, such as: 1) Therefore, there cannot be a simplest solution. 2) Therefore, there is ALWAYS an opportunity for a reduction to be discovered. [1] https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity
  - crimsonalucard 6y ago
    >1) Therefore, there cannot be a simplest solution. I never said this, I said that you cannot verify that the current solution you have is the simplest solution. This is based off of science, nothing can be verified science. Because we treat software more as black box experiments rather than formal systems, verification of your solution as the simplest solution is impossible until you define formal axiomatic rules. But again, this is basically never done and Even than you'd have to deal with Godels incompleteness. >2) Therefore, there is ALWAYS an opportunity for a reduction to be discovered. There is always opportunity in the sense of "possibility" if a solution hasn't been formally verified to be its' simplest. 2 follows from the notion that complexity cannot be verified. > [1] https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity From your wikipedia source: "The notion of Kolmogorov complexity can be used to state and prove impossibility results akin to Cantor's diagonal argument, Gödel's incompleteness theorem, and Turing's halting problem. In particular, no program P computing a lower bound for each text's Kolmogorov complexity can return a value essentially larger than P's own length (see section § Chaitin's incompleteness theorem); hence no single program can compute the exact Kolmogorov complexity for infinitely many texts." The above states that the exact Kolmogorov complexity can never be computed for all texts and that this fact has been formally verified axiomatically. Doesn't this support my overall point? If you can't verify the complexity of a piece of text than you can't verify if it's the least complex because you don't even know the complexity let alone whether its' the least complex.
aspenmayer 6y ago
I would rephrase this as “the solution can be as simple as your model of the problem but no simpler.” A better model, structure, implementation, or restatement of the problem could transform the dimensions of the problem space radically. But I do agree with you in spirit of what you said, that there is some essential “hardness” of the problem that is part-and-parcel with the difficulty in stating or explaining the problem. I see a similar complexity in representing the problem in code or functions or algorithms etc. Then comes a related issue with reducibility; some concepts or problems cannot be broken down into smaller discrete parts. They are already as simple as they can be. This is ideal in a certain sense, in that the concepts can be explored with fewer assumptions. However when someone asks you to explain like they’re 5 years old, interpretation and perception starts to creep in through intuitions and abstractions.
zmmmmm 6y ago
> I phrase it as "The solution can be as simple as the problem but no simpler" Even that can be deceptive. For example, I can state very simply: I want to move my house 3 inches to the left It's a very simple problem right? How complex do you think the minimally simple viable solution is? It's about how the problem maps onto the constraints of implementation.
- artfish 6y ago
  I am certain this is some kind of fallacy, since "house" is an abstraction that would need to be broken down somehow. The result would not be a simple problem anymore. Sorry, no fancy words, just common sense.

spacedcowboy 6y ago

I take your point, but the complexity I’m talking about is what remains after you’ve done any readily applicable simplifications. Any normal task has an inherent level of complexity (“add one” is a very simple task, so can be reduced down as you point out). “Invert a matrix” is somewhat less reducible. “Calculate a quaternion” even less so, etc. We generally string dozens or hundreds of these simpler tasks into sequences to get what we want, and human understanding being what it is, there’s quite a difference in conceptual complexity between “fly the plane to [here]” and doing all that maths. There’s probably a relationship to subitising here as well, the brain does seem to be able to process small groups of things, even if it knows those things represent larger concepts, better than larger groups of things. This is just speculation on my part though.

crimsonalucard 6y ago
I got into a really deep conversation about this here: https://news.ycombinator.com/item?id=23042796 https://news.ycombinator.com/item?id=23042796 You may have seen it, it's in the same thread of conversation we're having. Basically there's actually axiomatic proof that you can never know if you applied all possible applicable simplifications. Therefore you can never know whether or not more complexity can be destroyed or reduced.

jes 6y ago

With respect, I’m not seeing how your first addOne example returns an integer one greater than its integer argument. Am I missing something?

crimsonalucard 6y ago
(x * 1) + 0 - x + x + 1 x + 0 - x + x + 1 x - x + x + 1 0 + x + 1 x + 1