Thinking up something
new
Philip
Sargent
27 July 2003
The most exciting, useful and world-changing discoveries are
those that enable and produce more new, exciting and world-changing
discoveries. Usually, these are a new way of looking at the world, such
as quantum mechanics or double-entry bookkeeping: where the
consequences may be multifarious and unpredictable, but are of a lower
order of invention than the original, potentiating
discovery.
What kind of discovery would
unlock an endless stream
of invention of all types? We might think that it's been been a
challenge to keep up with technolgies in recent decades, when we have
been
living with the consequences of microprocessors which quradruple in
power every three years, but how much more of a
challenge would be armies of
Leonardos and Ghandis.
Artifical creativity
It is not commonly known, but we now know a lot more about the
processes by which hard problems are solved, especially those which
require an inventive or creative step for their solution. We also have
the mathematics to describe some of these processes and to prove
theorems about what is and may be possible, and what remains to be
proved.
There is a general consensus that most invention and creativity
involves some kind of constrained generation of many ideas followed by
a filtering or selection process which eliminates the bad ideas.
Different types of problem emphasise either the generation or the
elimination step. Sometimes either strategy can be made to work as the
primary mechanism: chess-playing software tends to generate many, many
moves and then has sophisticated methods of elimination, whereas people
tend to constrain their generation so that they only have to chose
between fewer good moves. We also know that learning or training
improves both processes and that this works whatever representation
technology is used to encode the knowledge: genetic algorithms,
statistical training, neural nets or just weighting hard-coded
strategies.
In human beings, we know that a period of mental immersion in the
problem, working through many different aspects of its behaviour, is
best followed by a period of relaxation or some other activity: the
tale of Archimedes in his bath is characteristic. We don't know why
this is the case, though there are a great many sensible ideas.
However, this is one feature which has not yet been reproduced in
articifical creative systems, so it bears watching.
Engineering practicalities
It is a general feature of hard problems that the generation step is
explosive whereas the elimination step is comparatively
straightforward. In many ways, it is much easier to recognise a soluton
when you see it than it is to come up with it in the first place: "I
may not know much arbout Art but I know what I like." In fact, we can
define intrinsically hard problems as those where the number of
potential solutions to be generated expands exponentially with the
number of initial options or conditions. However we can generally find
a procedure for checking the solutions that takes takes a "reasonable"
time (by which we mean a polynomial relationship, rather than an
exponential one).
Humans are pretty good at spotting a good solution out of half a dozen
or so, and pretty appalling at spotting one out of half a billion.
Software has no such limitations on its concentration, so much of the
progress in creative problem solving over the past decades has been
with this kind of brute force approach, but on the "easy" side of
checking, not the hard side of generating. If we look more closely, we
see that the more important aspect is the generation. Beating humans at
elimination is a cheap trick, but beating them at generating only
potentially good solutions is much harder.
If I want to invite half my friends to a party, but I know that they
all have strong likes and dislikes and don't all get on with each
other, then if I have only 8 friends, I can sort out 4 who get on in a
few minutes (though I may need a pencil and paper). If I have 100
friends, then the lifetime of the universe would be exceedingly small
compared with the time it would take a supercomputer to solve it. That
is a hard problem. In this case there is no good way to constrain the
generation of possibilities; we could sort the friends and select first
amongst those who hate the fewest, but unless most of them get one with
nearly anybody, that will make little practical difference.
Innovating in the problem as well as the solution
Take the problem of designing a new type of mechanical latch, not more
than 5cm in size, to hold a drawer shut to prevent small children
getting at sharp knives. One could generate random 3D solid objects and
then animate them to see if they "latch". Or one could also take a
fixed set of mechanisms (levers, rachets, springs), and then generate
all conceivable assemblies. That might work. However, we know that
mechanical engineers will almost always solve this type of problem by
using the basic mechanisms, and then also innovating with extra
arbitrary 3D shapes to make lugs or sockets, and by combining functons,
e.g. so that the support of rachet is also the elastic spring. What the
creative designer has done is to create a new set of mental tools and a
new way of looking at the problem, before he even starts on generating
possible solutions, and a long way before he checks to see whether they
work or not.
Changing the "space in which the problem is set" is not some kind of
intrinsically human, mystical ability. Chemical engineers have for a
long time written software that decides an appropriate number and
interconnectedness of a set of heat exchangers, before it then
optimises their sizes and throughputs. Encoding the tools and problem
is itself just another problem. However it is usually another
intrinsically hard one.
Humans are particularly bad at generating solutions when there are
multiple objectives, e.g. siting an airport both close to city and yet
where it will not be noisy, or optimising a chemical plant so that it
runs safely (at a low temperature and pressure), productively (at a
high temperature and pressure), efficiently (so that the temperatures
and flowrates match wherever pipes join), profitably (so that by
products are minimized) and controllably. Humans are so bad at this,
that even software which only gets close to the right sort of answer is
a great improvement, but nevertheless some of the best improvements
have come from new concepts in restructiring the problem space: using
enthalpy rather than temperature, for example, as a way of
characterising the heat flows.
P≠NP
So what kind of magic wand could we wish for? We have one intrinsically
hard problem in two guises: generating new good potential solutions by
constraining the generation process cleverly, and the problem of
generating new ways to structure the problem in the first place - so
that the constrained generation later is easier and more productive.
The opinion of most mathematicians is that a large number of
identified,
intrinsically hard, exponential problems (about a thousand of them,
known as NP for
Nondeterministic Polynomial) probably
have no solution that can
be found in "reasonable" (P for Polynomial) time. However, this is an
opinion: no one has yet found a proof. The Clay Institute of
Massachussetts announced in 2000 a prize of $1m to whoever can either prove this or find a procedure that solves one
of these problems in polynomial time. This way of expressing the
mathematics dates from 1971, but the concepts derive from those of
Gödel and others in the 1930s.
While it is likely that that there is no "reasonable" solution to hard
problems, it is quite possible that no proof of this will be found. If
a reasonable (polynomial time) solution can be found, then the
consequences are profound. All types of creativity and innovation
become practical whereas before only special cases and isolated tricks
could be found, but in the short term, the difficulties that it
produces will be worse than the benefits. One of the problems that
becomes easy is decoding encrypted communications, so the consequences
for the banking system and the Internet would be extremely disruptive.
There are two more likely eventualities than finding that P=NP: quantum
computers could be constructed which can solve all NP problems in
reasonable time, or approximate methods are found which can find useful answers in reasonable time
for most NP problems. If
either of these come to pass, we can expect a flowering of creativity
that will change the course of human history.
Further reading
Emergence, John Holland. A treatise on constrained generating
procedures (cgp). Not an easy read, but thorough and written by the
inventor of the genetic algorithm.
Clay Institute Millenium Mathematics prizes
http://www.claymath.org/Millennium_Prize_Problems/P_vs_NP/