Monday, April 24, 2017

A note on integer problems.

It's surprising and intriguing that it is more difficult to solve many problems restricted to integers than it is to solve problems when the number are not so restricted. It's surprising because the possible solution set is smaller if it's restricted to integers. This indicates the math I'm aware of (if not math in general) is not fully employing the concept of "solving problems backwards". As a side note, from my reading of how they were able to derive most of the shortest possible solutions to the Rubik's cube (an "integer" problem where you have a short list of possible moves at each step), it seems they largely depended on a "working backwards" methodology.  Actually I'm not sure any optimization problem can do without "working backwards". It's how you generally solve problems in science, first stating the question to be answered which is really describing the end result you seek.  In another sense it's not surprising not being restricted to integers is easier because if you have more numbers to choose from, then maybe there is more flexibility in the outcome. I mean there are more potential solutions.  Also, most interesting problems are an attempt to optimize something and having a continuous set of possible answers might imply a continuous path from beginning to end that can be optimized over shorter paths and thereby the solution can be "smelled" out more effectively.  Integer solutions imply hit or miss steps (if-then?) all the way. All the important questions in life require a distinct choice. Back in 1998 or 2000 should you have bought and held Amazon or Yahoo?  There have been some serious and respected thinkers (like Richard Feynman) who have seriously considered the possibility that nature at its deepest level is digital. As a side note, sometimes we have to extend the potential solutions to the complex plane to find solutions.

In the above I have in mind situations where we have all the information.  Both the data for the input variables and the logical relationships that lead to known output variables.   In competitive economizing agents, if an agent wants to maximize the amount of money in his bank account, his choices depend on the effect of other agents (buyers, sellers, and competitors) who are acting in unknown ways on on unknown data.

No comments:

Post a Comment