4 ms·

In english we tend to use complexity to refer more to how intricate a system is rather then algorithmic run time. It's confusing because programming is involved

In english we tend to use complexity to refer more to how intricate a system is rather then algorithmic run time. It's confusing because programming is involved with the intricacy of systems in a big way. That's why imho, the word 'complexity' is actually a really bad naming choice. Typically when I refer to complexity, I refer to it as complexity in Design and structure. Programming deals more with this type of design complexity for which currently no theory exists. How do quantify whether one program is more intricate then another? How do we quantify whether the functional style is less complex then an object oriented style? There's no way. Since no theory exists, it largely comes down to using intuition and design to deal with complexity. In short, no theory required, only because no theory exists (yet).

tptacek 12y ago
Isn't that just another facet of the same concept? The property you're referring to as "intricacy" is quantifiable and scales with the kinds of problems a program solves.
- crimsonalucard 12y ago
  How is it quantifiable? Which is more intricate, Linux or Windows? I don't think that question is answerable in any way that's meaningful. If you ask anyone that question you get a lot of qualitative descriptions and opinions, nothing definitive.
  - tptacek 12y ago
    IPC boundaries, interface size, basic block count and CFG arity, number of different storage classes, number of different objects, number of different object lifecycles, &c. I'm not saying there's one best known way to measure the complexity of a system, just that it is measurable.
    - crimsonalucard 12y ago
      These are black box metrics, better then counting lines of code, but essentially never truly able to describe the complexity of a system. To my knowledge, there's not even a strict theoretical definition describing what complexity is.
      - tptacek 12y ago
        This seems like a discussion that ends in us arguing about the validity of the concept of a human soul.
      - crimsonalucard 12y ago
        >This seems like a discussion that ends in us arguing about the validity of the concept of a human soul. I disagree. There is a logical end, so long as either of us have the capability of admitting we're wrong.
SilasX 12y ago
That's still expressible through computational complexity -- in this case, you're talking about how many components of the system you have to change at in order to change one functionally-distinct thing, and how it scales with the number of components. Well designed systems allow you to change one module and leave everything else alone -- O(1). Others might require a change on both sides of an interface and be potentially O(n). Still others might require you to to test far-distant parts of the system because they leak an abstraction, and be O(n^2), making them hard to add on to. You can then characterize "difficulty of changing stuff" as the number of components increase, and it's right back to the format of a computational complexity problem.
- crimsonalucard 12y ago
  >Still others might require you to to test far-distant parts of the system because they leak an abstraction, and be O(n^2) I don't understand how the theory converts. How is it O(n^2)? How does changing and testing modules convert to this number? Describe a case thats O(n log n).
  - SilasX 12y ago
    My point was that different designs can be more or can be less scalable; poor designs require you to change lots of things to make one functionally-distinct change. There was no "it" (specific class of architectures) I was calling O(n^2), but an example case might be where all the interfaces assumed p fields, each with q bytes, then having one component pass more information would require updates to all components O(n) rather than just that one. I don't see how describing an O(n log n) system sheds further light on any of this.
vancan1ty 12y ago
Algorithmic run time is "time complexity." There are many different types of complexity which we can measure in some sense, including space complexity, energy complexity, circuit complexity, and architectural complexity. http://en.wikipedia.org/wiki/Computational_complexity_theory http://en.wikipedia.org/wiki/Computational_complexity_theory I agree with you that there seems to be no foolproof way to measure the overall "software complexity" of a piece of software. There are a lot of methods proposed, but none is provably optimal or even all that useful it seems. Search "Evaluating Software Complexity Measures" by Elaine Weyuker for a somewhat dated paper discussing the topic. I would be very interested if anyone had any recommended resources on the current state-of-the-art regarding software complexity measures. Seems to me the only way to measure complexity absolutely would be some sort of extension of the minimum description length principle -- what is the shortest way we could write the specification for the entire machine + software that runs on it. Of course this seems completely infeasible for any real world task.

tptacek 12y ago

Isn't that just another facet of the same concept? The property you're referring to as "intricacy" is quantifiable and scales with the kinds of problems a program solves.

crimsonalucard 12y ago
How is it quantifiable? Which is more intricate, Linux or Windows? I don't think that question is answerable in any way that's meaningful. If you ask anyone that question you get a lot of qualitative descriptions and opinions, nothing definitive.
- tptacek 12y ago
  IPC boundaries, interface size, basic block count and CFG arity, number of different storage classes, number of different objects, number of different object lifecycles, &c. I'm not saying there's one best known way to measure the complexity of a system, just that it is measurable.
  - crimsonalucard 12y ago
    These are black box metrics, better then counting lines of code, but essentially never truly able to describe the complexity of a system. To my knowledge, there's not even a strict theoretical definition describing what complexity is.
    - tptacek 12y ago
      This seems like a discussion that ends in us arguing about the validity of the concept of a human soul.
    - crimsonalucard 12y ago
      >This seems like a discussion that ends in us arguing about the validity of the concept of a human soul. I disagree. There is a logical end, so long as either of us have the capability of admitting we're wrong.

SilasX 12y ago

That's still expressible through computational complexity -- in this case, you're talking about how many components of the system you have to change at in order to change one functionally-distinct thing, and how it scales with the number of components. Well designed systems allow you to change one module and leave everything else alone -- O(1). Others might require a change on both sides of an interface and be potentially O(n). Still others might require you to to test far-distant parts of the system because they leak an abstraction, and be O(n^2), making them hard to add on to. You can then characterize "difficulty of changing stuff" as the number of components increase, and it's right back to the format of a computational complexity problem.

crimsonalucard 12y ago
>Still others might require you to to test far-distant parts of the system because they leak an abstraction, and be O(n^2) I don't understand how the theory converts. How is it O(n^2)? How does changing and testing modules convert to this number? Describe a case thats O(n log n).
- SilasX 12y ago
  My point was that different designs can be more or can be less scalable; poor designs require you to change lots of things to make one functionally-distinct change. There was no "it" (specific class of architectures) I was calling O(n^2), but an example case might be where all the interfaces assumed p fields, each with q bytes, then having one component pass more information would require updates to all components O(n) rather than just that one. I don't see how describing an O(n log n) system sheds further light on any of this.

vancan1ty 12y ago

Algorithmic run time is "time complexity." There are many different types of complexity which we can measure in some sense, including space complexity, energy complexity, circuit complexity, and architectural complexity. http://en.wikipedia.org/wiki/Computational_complexity_theory http://en.wikipedia.org/wiki/Computational_complexity_theory I agree with you that there seems to be no foolproof way to measure the overall "software complexity" of a piece of software. There are a lot of methods proposed, but none is provably optimal or even all that useful it seems. Search "Evaluating Software Complexity Measures" by Elaine Weyuker for a somewhat dated paper discussing the topic. I would be very interested if anyone had any recommended resources on the current state-of-the-art regarding software complexity measures. Seems to me the only way to measure complexity absolutely would be some sort of extension of the minimum description length principle -- what is the shortest way we could write the specification for the entire machine + software that runs on it. Of course this seems completely infeasible for any real world task.