Producing the shortest tour in the Traveling Salesman Problem (TSP) is intractable.
The term “intractable” is a technical term in Operations Research and
it refers to the fact that producing the shortest tour cannot be done in most practical applications.
Interestingly, humans always produce near optimal tours for TSP and they do it with a constant speed of 2-3 sec per city.
The small size of working memory and the fast solution times imply that the subject does not perform search of the problem space.
Instead, the subject changes the intractable problem into an ill-posed inverse problem of constructing a self-similar TSP tour.
By self-similar I mean that a tour is similar to itself across levels of scale and resolution.
Self-similarity in scale and resolution is a form of symmetry (more precisely a fractal symmetry).
This change of representation is accomplished in the visual system by using hierarchical clustering
to form what is called a multiresolution/multiscale pyramid representation.
So, the cities in a TSP could be randomly distributed, but the human mind imposes a self-similar (symmetrical) representation.
In the second half of the talk, I will discuss brainteasers and scientific discovery.
Brainteasers, called by Gestalt Psychologists insight problems, require changing mental representation from
the initial inadequate representation, to the adequate one.
Once you discover the adequate representation, you are likely to succeed in solving the problem.
When this happens, the subject may happily shout “AHA” or “Eureka”, as the proverbial Archimedes did.
There is a large collection of insight problems, but the problem with studying insight problems is
that they all are very different and there has been no hope of providing a theory of what happens to the representation and
how it is changed.
Insight problems are interesting and important because it has been quite universally acknowledged that scientific discovery
(e.g., heliocentric theory, Newton’s Laws, Einstein’s relativity theories) is the most sophisticated version of an insight.
But with little understanding of ordinary brainteasers, formulating a theory of scientific discovery was not in sight, either.
I started by looking at scientific discovery with the plan of learning about ordinary brainteasers.
The history of scientific discoveries in physics clearly shows that a new theory has always been formed by adding
a new symmetry to the previous theory (think about substituting heliocentric theory for a geocentric one).
Can discovering symmetries be a key to insight problem solving, as well? The review of a number of brainteasers suggests
that this is indeed the case.