Impossible Problems Arising from Complexity

Impossible Problems

by

Don Allen

Impossible problems are everywhere.  They are in your life, your friends’ lives, your work, your family, your dreams, your future, and your expectations.  No matter what you do, no matter what you try, you can’t avoid them.  Impossible problems come in many flavors.

·         Problems you can’t solve

·         Problems than change when you try to solve them

·         Problems solved on the basis of past knowledge

·         Problems involving a change of scale

·         Problems about systems exhibiting memory

In this note, we take up the nature of impossible problems.  We will illustrate some, but naturally we cannot solve them.  We’ll consider these topics, though the last one is problematic.

·         Definitions

·         Categories

·         Sources

·         Creating

·         Solutions

But we should begin with the nice problems – those that actually have a solution, and not only that a unique solution that behaves itself.

Well Posed Problems.   Being as they are, mathematicians and all scientists love to solve problems, but they want to know their problems have a solution, and that the solution has certain very nice properties.   This is notwithstanding finding the nice solution may be really difficult.     The consequence is that there has evolved a classification of problems.  This is the basis of the so-called well posed problem.  Well posed problems have three components.

1.      A solution exists.

2.      The solution is unique. A solution is considered to be unique, i.e. the only one, when no other solution meeting the criteria of a solution can be constructed using the same data or information.

3.      The solution's behavior hardly changes when there's a slight change in the initial conditions.

Indeed, some very important research papers have focused completely on showing certain actual problems are well-posed. Strange as it may seem, long before a problem is solved, it is important to show there is actually a solution, and hopefully a nice one. Here is a simple one that does not have a nice solution, i.e. is not well-posed. Solve

x - 3y = 4
2x - 6y = 5

Of course, these represent two parallel line that do not intersect, and therefore there is no solution, much less a unique solution.

These are the problems we work with all the time.  These are the problems we give our students with the undiminished hope they can solve them.   These are the problems we think of “as problems.”  Mostly we are not concerned with the third point, as seldom do we change the parameters of a problem and expect nothing other than small changes in the problem result in small changes in the solution.   A problem not well posed is often called ill-posed.   Ill-posed problems are the bane of the sciences, but the grist of almost all other endeavors.  Ill-posed problems constitute the great preponderance of problems in life.

Solutions.  A problem has a solution if and only if there can be posited a resolution to the situation that is essentially irrefutable except by rejecting the premises applied.  Solutions must be obtained their merit upon the clarity of the reasoning, and in some cased be reproducible.  Steps toward the solution must follow an accepted path with no hidden information suggested or interjected.

Difficult Problems.  Before tackling impossible problems, it is instructive to consider the notion of difficult problems. How can we, as ordinary type folks, make a difficult question?  That is, how can you and I pose questions that have no clear resolution, much less a solution?  What does a resolution or solution mean?  Who is the arbiter of correctness?  These, in themselves are difficult questions.  Channeling down this path would lead to yet another chapter.   Let’s just work on difficult.

A problem is regarded as inherently difficult if its solution requires significant resources, whether of a human, computational, mechanical, economic, or physical nature.  There are many of these.  Examples. (1) Send a human to the moon with a return ticket.  (2) Cure cancer.  (3) Prove Fermat’s last theorem (i.e. show there are no positive integer solutions to x^p + y^p = z^p when p is a positive integer greater than 2.   Two of these problems have been solved, both with huge expenditure of resources, but the cure for cancer inches along slowly even with massive talent and technology applied. Indeed, the solution of Fermat’s theorem involved hundreds of mathematicians over more than three centuries.  These and other problems such as the grand challenge problems[1] are difficult, but thought to be possible.

Impossible Problems.  At this point we have the well-posed problems and difficult problems, though there may be considerable overlap between them.  What about impossible problems?  These are more easily described using our paradigm of difficult.  We’ll say a problem is impossible if its difficulty cannot be imagined within the toolkit of current expertise.  It is impossible if there is no possible, no conceivable, or no realizable plan to solve it. 

The good news is that some formerly impossible problems were promoted to merely difficult, and then at last solved.  Example:  Through vaccinations cures for hundreds of diseases now exist.   These cures were impossible before the nature of the living cell was discovered and then the notions of bacteria and viruses. In fact, the path of modern medicine is littered with countless attempts to solve impossible problems by merely treating symptoms, and then often without success.   Going from impossible to merely difficult often involves a conceptual innovation and/or a paradigm shift.  Yet, as we’ll see there are impossible problems that will likely always remain so.

As further amplification, an impossible problem usually has one of the following characteristics:

·         It has no solution.

·         It has multiple solutions.

·         It has partial but incomplete solutions.

·         It has complex solutions.

·         It has incomprehensible solutions.

·         It involves incomplete or inconsistent data.

·         It involves semantics (often in the form of a paradox).

There are more characteristics, to be sure, but these will do for now.  Examples of impossible questions include (a) Is this or that opinion true?  Eg. Kenysian economics, God, etc, (b) Has man caused global warming?  (c) Is global warming an artifact of natural processes? (d) Paradox type questions?, and (e) Vague questions.  Regarding the latter, we note that many impossible questions are just that because they are vaguely stated.  We could eliminate this category, but then we are faced with making a definition for a “clearly stated” problem.  Yet another dozen paragraphs with all sorts of qualifications would result. 

Generic sources of impossible problems include the likes of (i) Which is better?  Which is true?  In the absence of precise criteria. (ii) What will happen if?  (iii) Is what we think is true actually true everywhere? (e.g. speed of light), (iv) At what point do we reach the micro from the macro (heap paradox)?, and (v) Are we working with a model? Each of these need ample discussion. However, it is (iv) that we single out.  The micro-to-macro transition is the source and reason for many impossible problems, for the simple reasons that we apply micro- or macro- knowledge to the opposite, never knowing when the one becomes the other. For example, individuals behave quite differently from groups and these in turn quite differently from societies. On the other hand, water molecules behave quite differently from streams and these quite differently from oceans.  (We never discuss tidal aspects of a small stream.) One aspect usually cannot be used successfully to analyze the other.

There are more examples. The problems have no discernible solution.  Can you identify the problem(s) with these problems?  Many are vague or seek opinion or require a particular set of beliefs.  All are impossible for at least one of these reasons.

·         Which is the better color?  Red or Blue?

·         Should we go to war on the basis of human rights violations?

·         Does the current food stamps program lead to job growth?

·         Do the merits of a Mars landing equal the costs of doing so?

There are numerous sources of impossible problems.  Not just opinion or vague types, these are the reality of our natural world. They can be ignored by the ignorant but cannot be dismissed.

·         System Complexity - entropy

·         Stability issues

·         Conflicting information

·         Quantum effects

·         Self Organization

·         Fundamental constants

·         Macro-micro transitions

·         Politics, economics, religion, societal

·         Data mining

·         Semantics

In this short note, we consider just the first - complexity.  Few of these systems are of a fully scientific nature, much less mathematical. Most involve many factors including the political, economical, biological, sociological, and more, and finally all would-be solutions combine analytic, logistic, and tactical aspects.  As well, we need to include the tools of inference, intuition, and induction as factors in their consideration.

Complex Systems. In our remaining paragraphs we will detail more about complex system and now they can create impossible problems.  Complex systems have several features, each seemingly more complex than the previous. 

•     
 Open and closed systems. Too many problems are regarded as arising in and confined to closed systems.  In fact, many problems are not closed-contained but open, meaning it is a problem that continually interacts with its surroundings or environment.  Solving open system problems without an encompassing view can lead to a cascade of system failures.  Closed systems are basically the "in-the-box" systems, where what we do is confined to the often small box in which they are addressed.

•       
Nonlinearity.  Complex systems offer us the nature of nonlinear responses.  Assuming that a measure of this facet or that in this level or that may result in a proportional response is often completely incorrect.  Complex systems respond nonlinearly, meaning that quite a small change, via problem solution, may result in a very great change in the system itself.

•     
 Hysteresis is the dependence of a system not only on its current environment but also on its past environment. This dependence arises because the system can be in more than one internal state.  But this is one thing most of us understand.  However, to rely on solutions based on its past environment is a clear and present danger.  You cannot solve the problem on the basis of what was.  This implies the importance of engaging “new blood” into your problem solving team. (Hysteresis occurs in ferromagnetic materials and ferroelectric materials.  This implies our social, political and economic systems have this signature)

•       
Memory is a facet of complex systems.  They “remember” where they’ve been, and even though the circumstances may have changed in their dynamics, they still have an aspect of system memory, meaning that prior states may still have an effect on their current performance.   This memory may impact current solutions, possibly indirectly.

•       
Scaling.  Many complex systems range over numerous scales of action.  While effects between scales may not be obvious, apparent, or even strongly considered, they are a part of the grand system.  These interact to an extent with the micro-macro scale but in a fully integrative manner.

•       
Feedback Loops.  What is ever present in dynamical complex systems is the feedback loop.  This means that actions at this time alters the system for future times.   This makes key, the idea that any problem solution may not only change the system but nullify the carefully constructed solution.

•       
Computability. These may be the most familiar of all.  Can we compute the solution?  Is there an algorithm to generate a solution – and in a reasonable time?  Note, it is not uncommon for some resolutions to take months on a super computer.  These are the easy ones.  What about problems that would take centuries?

Other features of complex systems are known, unknown, but studied. Some involve information available, cascading failures, emergent phenomena, nonlinearity, and multiplicity.  All highlight the issues surrounding complexity of the problem.  Many involve discovery what the problem may be.  However, we can postpone all these to another day, where more time is available.  We conclude with six more examples, many of which you know.  However, now your viewpoint may be of impossibility and not just for you but for everyone.

Six more examples.  

•      Chess. Does the person that moves first in a game of chess have a lock on winning, losing, or a draw?  (Game theory)  This game is so complex that any attempt at computing a solution is nearly beyond reality.  Indeed, even the fastest of fastest super computers programmed to play chess have difficulty seeing even five moves ahead at any given game state.

•      Butterflies. When a butterfly flaps its wings in Tokyo, how does this affect the weather in Rome? (Chaos theory)  The quintessential problem arising from chaos theory, this involves certain complexities but also instabilities both of which eclipse imagination.

•      Primes. Given an arbitrary number of 1,000,000 digits.  Is it a prime? (Mathematics) Here we are not discussing a number with value in the millions, but a number with a million or more digits.  Such a number would require several volumes simply to print.  The determination of primality (i.e. can be divided only by itself and one) of such large numbers is really beyond the capacity of even quantum computers, if they could construct one. This is a problem we know has a solution, and a unique solution, but it is impossibly difficult.

•      The spoke. If a spoke is balanced on its end, it will topple over.  Where, exactly, will it fall? (Stability theory) Ok, take a bike spoke, or even toothpick.  Balance it upright and release.  It will fall over; you know it.  But exactly where will it fall?  Again, this problem may not have a unique solution owing to complexity or possibly instability.

•      Evolution. How will the human species evolve?  (Bio-complexity)  Here is one of those gee-whiz problems, but a tough one.  First of all, we need a further development of evolution theory.  Then we need to understand all the factors that may contribute to human evolution.  Finally, we would need to construct a model that incorporates all this.  However, putting any solution into effect may have the consequence of changing how the evolution works.  A far simpler problem would be the determination of how the stock market works. If you could so discover this and made it known, that fact would change how the market works.   

•      Traveling salesman. What is the solution to the traveling salesman problem? (Computational) Suppose a salesman must travel to n cities.  What is the minimal length of the distance he/she must cover to make a complete circuit.  It is a big-time problem with applications in planning, logistics, and the manufacture of microchips. This, our last example, is a problem that we know has a solution, though whether it is unique is unknown.  First formulated in the 1930’s it has been around since the 19^th century.  It has been solved in a number of cases with a large number of cities, but the computational efforts to do so are immense. It appears there is no theoretical solution (and if there was one it may be incomprehensible), though very good computational solutions can be obtained.  This problem ranges between the most difficult and impossible.

In conclusion, we hope you, having seen many examples in your world,  are convinced many types of impossible problems abound.  And note, if you will, we have substantially only worked with a single source for impossible problems – COMPLEXITY.

Note. I’ve made an abbreviated video of this article.  You can find it on YouTube at http://youtu.be/c43AsHoYppA.

---

[1] See http://en.wikipedia.org/wiki/Grand_Challenge, for example, the grand challenge problems in science or engineering.