Thursday, April 20, 2017

Problem Definition

Defining “problem” is a bit difficult because things quickly get philosophical.  A thief trying to rob a house might view a wall around the house a problem.  The owner of the house might see the wall as the solution.  The dog hidden behind the wall sees the wall as a problem because he can’t get to the thief.  Which means the wall isn’t a problem for the thief.  It’s actually a solution to keep the dog away.

I want to avoid perspective, subjectivity, and needing perfect prescience.  Instead of dealing with all possible meanings of “problem”, I’m going to go with a smaller scope.  Cognitive complexity [1] is my idea that some problems really are harder for people to deal with than other problems.  More or less think of it as the human equivalent to Computational Complexity.  A problem as I’m thinking of it is a graph of spaces (vaguely similar to a category) where you pay specific attention certain qualities of the spaces and the connections between them.




Each blob is a space or set that contains all of the valid options for transitioning to the other blobs via the arrows.  The idea is that you’re modeling your problem as a series of actions (the arrows) that you can take and the result of the action you’re taking (the blobs).  

However, something isn’t quite right because some of these spaces have multiple arrows entering and exiting.  Does the space somehow account for the valid inputs to multiple different blobs?  Well, the image is a simplification.  Really each blob is a collection of blobs.  Each arrow leaving a blob will have it’s own blob that encodes the valid inputs for that arrow.  Additionally, each arrow entering a blob will have a blob that encodes all of the possible outputs from that arrow.


The complexity part comes from analyzing the blobs, the relationship between the arrows and the blobs, the arrows themselves, and the relationship between the collection of blobs in any given “superblob”.

Qualities of a blob

 * The blob should be a valid metric space.  This allows you to exploit the intuition that comes from having a metric space.
 * The blob should be a low dimensional space.  High dimensional spaces have some weird characteristics that can make them hard to reason about. 
 * The blob should be path connected.  This allows you to summarize the blob with an indexing function.  In this way even complex blobs can be reasoned about.
 * The blob should have a minimal number of holes.  Holes cause problems with intuition because what looks like a valid sequence of inputs may contain hidden traps.

Qualities of the relationships between arrows and blobs

Any given arrow, valid input blob, and output blob should create a function that is continuous.  Continuous functions are great for intuition because by only knowing the behavior of a small set of inputs you more or less know how related inputs will also behave.  Discontinuous functions can send an input that is similar to a familiar input to a vastly different output.  This can be problematic when you need to reuse the output in a context where there are many different invalid choices.

Any given arrow, valid input blob, and output blob should create a function that preserves the structure of the objects being sent through them.  There’s some more explanation as why this is valuable for comprehension in [1].

Qualities of arrows

Take all of the arrows and create a meta blob that describes it.  Now you can use the qualities of a blob to determine the complexity of the arrows.

Qualities of the sub blobs in any given super blob

Ideally all of the sub blobs that make up the super blob should be an identical blob.  This would mean that however you get to a certain blob the value that you end up with can be sent to any other blob via any other arrow leaving your blob.  When the sub blobs aren’t identical you will run into problems because it means that sometimes when you enter a blob there are some exit arrows that you can’t legally take.  There has to be some overlap between output blobs in the super blob and valid input sub blobs because otherwise you would not be able to ever leave the blob you enter even if it looks like there are exit arrows (*something* is going to go wrong when you try to transition away).  The more complex the overlap the harder it is to know when you can correctly transition out of a super blob.  Even worse, the overlap may be 99% the same, but the last 1% difference may be a hidden trap that will be completely missed until you’re in a position where failure is not acceptable.

Like the qualities of arrows you can create a meta blob to track the overlap between sub blobs in order to determine how bad the situation is.