Subject: Summary: Conservation of Difficulty

From: <[email-masked]>
Date: Mon, 11 Mar 1996 11:48:56 -0700 (MST)

Dear netters, 

here is my summary to the posting of the "Law of Conservation
of Difficulty". 

I was truly amazed by the large number of responses I got.
Appareantly, I found an interesting subject. 
Reading the responses was indeed a pleasure for me, therefore
thanx to everybody who wrote! There are some really good thoughts
hidden in this rather lengthy summary ...

There seem to be two types of responses to this "conservation law".
A number of writers agree (more or less) to my "law" and add
some aspect or another to it. The other group points out
that "Reducing the difficulty" is what science is all about,
see, e.g., the example of the Maxwell equations in Vitaly Rassolov's
mail.

Before coming to the actual summary, I want to give proper
credit, since I didn't "invent" this myself. Rather, I heard it in
1988 from Prof. H. Eschrig, Dresden, Germany.

----------------------------------------------------------------------
----------------------------------------------------------------------
This was my original posting:
----------------------------------------------------------------------
----------------------------------------------------------------------

Hi everybody,

a couple of years ago, one of my theoretical physics
professors cited the "Law of Conservation of Difficulty".
I thought I should share this law with the computational
chemistry community on the net.

As the name suggests, the law states that the difficulty 
of a problem is conserved, no matter how you reformulate it. 
I will demonstrate this by a few examples.

Take Density functional theory (DFT). We start off with the 
terribly complicated Schroedinger equation -- for the electrons
in a molecule, say. We reformulate it in a very clever
way to obtain DFT. Now what have we got? Indeed, we have a
beautiful formulation of the same problem: the basic variable
is the density, an observable that depends on three coordinates,
rather than 3*N as is the case with the wave function.
Thus, the problem has been simplified considerably.
However, all the difficulty comes back in the exchange-correlation
functional. (Remember that its functional form is unknown).

Another example is given by Molecular Mechanics. Again, the
very difficult problem of the time-dependent Schroedinger equation
is reformulated as simple classical equations of motion.
However, the difficulty is conserved. In this case, it pops up
in the necessity to obtain reliable force fields.

I suppose I have to modify the law somewhat since it is certainly
possible to make life MORE complicated (by doing lots of stupid
things). Maybe the "difficulty" is an entropy-like property?

Does anybody want to comment on the above?
If so, then I shall summarize to the net.  In particular, I
would like to get a reference ...

Yours, Georg

P.S.   Don't take me too serious on this one ...

----------------------------------------------------------------------
----------------------------------------------------------------------

And these are the various answers:
----------------------------------------------------------------------
----------------------------------------------------------------------

Huang Tang writes: ([email-masked])

Interesting law :-) I would go further to apply the law of ever
increasing entropy: you never replace a single (complicated) work with
a single simpler work.  So, DFT and MM replace ab initio work with
many, many trivial, time consuming small jobs to tackle each problem.
On the human side, we diverse a single work supposedly done by
computer (say solve the HFR equations) to many smaller jobs for us
(constructing force field.)

Cheers...

Huang TANG
----------------------------------------------------------------------

Richard A Caldwell <[email-masked]> writes:

This reads like it's related to what I have always called "Caldwell's First 
Law:"

	"To solve a problem, you must first create it."

Have a good day,

Dick CAldwell
----------------------------------------------------------------------

Randy J. Zauhar writes:

   George,

      That is an excellent observation. Indeed, I think there is an
  entropy/complexity issue in this. In a system with complex interactions
  (i.e. a system of protons and electrons) you can try to "condense" 
  obervables together (as in your example of particle density in DFT) - 
  neverthless, to make predictions about that system, your model must 
  somehow take into account the information embodied in the various 
  interactions found in the original system. If you are lucky, the information
  in those interactions is unimportant for the predictions you want to make,
  in which case you can create a simple and useful model - if not, then 
  the complexity you threw away must be reintroduced somewhere else. 

      I am sure that physicists with interest in information theory have
  thought long and hard about this.

       Regards,

       Randy

All opinions expressed here are mine, not my employer's

///////////////////////////////////////////////////////////////////////// 
\\ Randy J. Zauhar, PhD             | E-mail: [email-masked]        //
\\ Tripos, Inc.                     |       : [email-masked]           //
\\ 1699 S. Hanley Rd., Suite 303    |  Phone: (314) 647-1099 Ext. 3382 //
\\ St. Louis, MO 63144              |                                  //
/////////////////////////////////////////////////////////////////////////
**                                                                     **
**  "If you have conceptions of things that you can have no conception **
**   of, then the conception and the thing appear to co-incide."       **
**   --- C.G. Jung                                                     **
*************************************************************************

----------------------------------------------------------------------

Vitaly Rassolov writes  ([email-masked])

As far as I remember, Mach (the same as in Mach number of hydrodynamics) said
that the purpose of science is to save time.  That is, by discovering general
laws we spare followers from unnecessary details.  It seems to me that such
view of science is closely related to "Conservation of Difficulty":  the purpose
of science becomes the reduction of difficulty.  Indeed, if we simply reformulate
the problem, the degree of difficulty remains the same, so no science was per-
formed.  However, the truly valuable scientific contributions are precisely
those which help to deal with difficulties.  Maxwell equations, for instance,
greatly simplify building of electrical devices (i.e. reduce difficulty in their
construction).  If one adheres to such view, the law on "Conservation of
Difficulty" becomes the measure against which we can check the progress of
science.
			Vitaly Rassolov
			Northwestern University

----------------------------------------------------------------------
"Robert W. Zoellner" <[email-masked]> writes

Subject: Conservation of Difficulty, perhaps

Just an aside to your perhaps basic law of nature:

I recently built a deck outside of our house, and decided that digging the
holes for the supports would be too difficult using only hand tools such as
picks, shovels, and the like (even with my friend helping).  So, I rented a
gas-powered auger, for two men, to do the job.  The upshot of all of this was
our conclusion:  The work needed to do a job does not change with the tools
used:  All that changes is the intensity of the work during the time needed to
finish the job.  We were just as tired after drilling one hole with the auger
as we were after digging one hole with our hand tools.

Thus, not only the conservation of difficulty, but a conservation of work and
effort!  A loose application to computational chemistry is possible, I suppose,
in that you begin with semi-empirical methods because that is all that your
computer can handle in a reasonable period of time, and then move to ab initio
when you can afford to, but the overall effort required is probably about the
same, especially when you factor in the time it took to get the proper computer
for the job!

Oh well....

Have fun with your question!

Bob Z.

----------------------------------------------------------------------------------
Hugh Kennedy writes ([email-masked])

Simplifications and compressions are always possible: that's what science is
all about; without them, our models and calculations would be as complex as the
natural systems we are trying to understand.

Hugh Kennedy

----------------------------------------------------------------------------------
Dave Young writes: (this article was posted on the list and produced some spin-off
                    discussion)

Georg writes:
>
> a couple of years ago, one of my theoretical physics
> professors cited the "Law of Conservation of Difficulty".
> I thought I should share this law with the computational
> chemistry community on the net.
> 
> As the name suggests, the law states that the difficulty 
> of a problem is conserved, no matter how you reformulate it. 
> I will demonstrate this by a few examples.

	I will agree that there are very often trade offs in the
difficulty of methods.  However, I will not admit to any sort of 
law of conservation.  Let me give a counter example.

	Consider the solution of the Schrodinger equation for
the hydrogen atom.  If we did not know the exact solution we could
put incredible amounts of work into extremely accurate calculations
using DFT, GTO expansions, cubic splines, polynomials, etc.

	Now consider how difficult hydrogen atom calculations could
be even knowing the exact solution.  The logarithm and exponential
functions have proven so useful that they have been built into 
calculators and programming languages and reliably return results
to the precision of the machine.  If this were not the case, we would
have to spend quite a bit of time making sure that we are accurately
computing exponentials and logarithms, or we could have an enormous
database holding a table of logarithms ( 60 years ago every scientist and
engineer had a table of logarithms handy at all times ).

	Now extrapolate from our current state of theory.  If we knew
the exact analytic solution to the Schrodinger equation for molecules
most of what we do now would be trivial on the smallest PC.
This would still not prevent computational chemists from eating every
bit of computer power in sight as they tried to either deal with
relativistic effects or the transport of drugs through cell wall 
membranes.

	Although computers are incredibly powerful tools that I would 
not want to live without, they have also made us lazy.  In the past
such scientific problems would have either been shelved until the
mathematicians had come up with a technique for solving it or scientists
would have worked on it until a solution was found.  Although numerical
techniques allow us to jump past the development of mathematics,
sooner or later we will have to go back and get the original problem
right.  I firmly believe that the Schrodinger equation will one day
be as easily dealt with as trignometric functions on a calculator.

	Now ask your self two questions.

1.  How important would it be to work on an analytic solution to
the Schrodinger equation?

2.  What would be the chances that you could get funding for this 
project?

	I will let you draw your own conclusions.

                                Dave Young
                                [email-masked]

==========================================================================
     No assumption or approximation is reasonable for all cases.

 Corollary:

     Assumptions must be both rationalized and checked.
          But it is more important to check them.

--------------------------------------------------------------------------
--------------------------------------------------------------------------

David writes <[email-masked]>

Equivalence of computational complexity is well known.  If you could solve
the traveling salesman problem, you could solve many other difficult computing
problems.  By gross extrapolation, not only have alot of smart people been
trying to find simple analytical solutions to the solutions to the many body 
Schroedinger equation without success, many more people in other fields have 
been working on problems that are computationally equivalent, also without 
success.  If there is a simple solution, finding it certainly is not easy!

That most of the problems we have solved tend to have simple solutions 
(Occam's
razor), does not imply that all problems have simple solutions.  Maybe we just
are not smart enough to solve the problems with really complicated solutions. 
 The conclusion from computer science is that there seem to be whole classes 
of problems that are just plain hard.

David
--------------------------------------------------------------------------

Konrad Hinsen writes:
Cc: [email-masked]

> right.  I firmly believe that the Schrodinger equation will one day
> be as easily dealt with as trignometric functions on a calculator.

Which means by numerical approximation ;-)

Seriously, I wonder what your confidence is based on. Of course it may
be possible to find further analytic solutions, but I don't see why
this should necessarily be true. Much less do I see how you can make
such a claim for *all* applications of the Schroedinger equation.

Of course all this depends on what you call a "solution". In the case
of trigonometry, all we have is a set of analytic relations between
various functions that often occur together. With the exception of a
few special cases, there is no "analytic" answer to a trigonometric
problem, in the sense that the result cannot be expressed in simpler
functions (i.e. sums, products, and powers). A comparative level of
"solution" of the Schroedinger equation would be a safe numerical
procedure that can find the solution to any problem to a specified
accuracy. This procedure could then be put into the theoretical
chemist's equivalent of a pocket calculator. If that's what you mean
by solution, I agree that it will probably one day be available.

-------------------------------------------------------------------------------
Konrad Hinsen                     | E-Mail: [email-masked]
Departement de chimie             | Tel.: +1-514-343-6111 ext. 3953
Universite de Montreal            | Fax:  +1-514-343-7586
C.P. 6128, succ. Centre-Ville     | Deutsch/Esperanto/English/Nederlands/
Montreal (QC) H3C 3J7             | Francais (phase experimentale)
-------------------------------------------------------------------------------

Liang writes  ([email-masked])

On Mar 5, 12:48pm, <[email-masked]> wrote:
>
> a couple of years ago, one of my theoretical physics
> professors cited the "Law of Conservation of Difficulty".
> I thought I should share this law with the computational
> chemistry community on the net.
>
> As the name suggests, the law states that the difficulty
> of a problem is conserved, no matter how you reformulate it.
> I will demonstrate this by a few examples.

Seems that the difficulty of obtaining the exact solution is conserved.

>
> Take Density functional theory (DFT). We start off with the
> terribly complicated Schroedinger equation -- for the electrons
> in a molecule, say. We reformulate it in a very clever
> way to obtain DFT. Now what have we got? Indeed, we have a
> beautiful formulation of the same problem: the basic variable
> is the density, an observable that depends on three coordinates,
> rather than 3*N as is the case with the wave function.
> Thus, the problem has been simplified considerably.
> However, all the difficulty comes back in the exchange-correlation
> functional. (Remember that its functional form is unknown).
>

Seemingly you are not enjoying the saved computer time for the O(N^4) HF
exchange calculations and growingly feel annoyed by the inherited inaccuracy.
 The God solves SEs exactly and He bleesed by giving chances to measure the
observables as His own SE solutions. The not blessed has to model the world
approximately. I do not bother with this law. As long as there are still ways
to go around the most difficult and possibilities to trade the last few percent
accuracy for the time needed to draw a picture of any quality anyway.
The real artists possess the perfectness and the exactness.

> Another example is given by Molecular Mechanics. Again, the
> very difficult problem of the time-dependent Schroedinger equation
> is reformulated as simple classical equations of motion.
> However, the difficulty is conserved. In this case, it pops up
> in the necessity to obtain reliable force fields.
>

I dreamed of living a simple life: doing things with one method never trying a
second. Will trust the ConsumersReport to find the best buys as long as the
magzine is reliable. Buy the simplest camera equipted with the most
sophisticated computer chip. If not yet available, demand one from the
manufactures.

>
> I suppose I have to modify the law somewhat since it is certainly
> possible to make life MORE complicated (by doing lots of stupid
> things). Maybe the "difficulty" is an entropy-like property?
>

Agree. And I hear the LAWd saying: minimize the entropy on your own; let it
grow elsewhere. The buddism advises not to take any initiatives so that the
total entropy could be conserved.

>
> Does anybody want to comment on the above?
> If so, then I shall summarize to the net.  In particular, I
> would like to get a reference ...
>

Done.

> Yours, Georg
>
> P.S.   Don't take me too serious on this one ...
>

It's really a fun to read the broadcasting and write the comments.

Have a good day!

Liang

-------------------------------------------------------------------------------

Michael K. Gilson writes  ([email-masked])

The discussion raises the following possibly naive question:

Are there mathematical problems that can be solved analytically,
whose numerical solutions look like hard, NP-complete problems?

Mike

-------------------------------------------------------------------------------

Jan Reimers writes

> Take Density functional theory (DFT). We start off with the 
> terribly complicated Schroedinger equation -- for the electrons
> in a molecule, say. We reformulate it in a very clever
> way to obtain DFT. Now what have we got? Indeed, we have a
> beautiful formulation of the same problem: the basic variable
> is the density, an observable that depends on three coordinates,
> rather than 3*N as is the case with the wave function.
> Thus, the problem has been simplified considerably.
> However, all the difficulty comes back in the exchange-correlation
> functional. (Remember that its functional form is unknown).

I have never found DFT to be that beautiful, I don't understand what it
contributes beyond what J.C. Salter already showed us years before
with his Chi-alpha approximation to exchange function.  Besides the reduction
>from 3N to 3 coordinates is essentially the one elctron approximation,
The mean field approximation, the product wave function approximation,
or whatever you want to call it.  Its not specific to DFT.
	If Kohn and Sham told us how to evaluate the kinetic energy as
a functional of the density, then I would say DFT was "beautiful".
Since we don't know how to do this we expand the density as sum of
occupied orbitals, and we are right back to Slaters formulation.

	In exchange (no pun intended) for making approximations you
get reduced diffictulty.  So in this sense DFT does not conserve
difficulty.  You appriximate Vxc with some empirical functional,
and you fit the density and Vxc with an auxillary basis, and it all pays off
by reducing an N**4 compution to and N**3 computation.

	Does saving computer time count as dercreased difficulty, our
are you using a more abstract (subjective?) definition?

> 
> P.S.   Don't take me too serious on this one ...
> 

OK

+--------------------------------------+-------------------------------------+
| Jan N. Reimers,  Research Scientist  | Sorry, Don't have time to write the |
| Moli Energy (1990) Ltd. B.C. Canada  | usual clever stuff in this spot.    |
| [email-masked]                |                                     |
+--------------------------------------+-------------------------------------+

--------------------------------------------------------------------------------
John Reissner writes:

What I always heard about "C.o.D" was that it referred to
the fact that while solved problems seemed easy in retrospect,
("the easy problems have all been 'picked off'"), in fact 
historically all problems were equally difficult,
i.e. just barely soluble.

John

John Reissner         Pembroke State University     Pembroke NC  28372  USA
[email-masked]     vox: (910)521-6425    fax: (910)521-6649

--------------------------------------------------------------------------------
Ole Swang writes ([email-masked])  

>As the name suggests, the law states that the difficulty 
>of a problem is conserved, no matter how you reformulate it. 

Interesting view, and the observation seems empirically true.  As for
reasons, I have the feeling that it doesn't necessarily express some
mystical property of nature - except that nature is more compicated
than any model we will ever come up with. I would like to put forth
some loose thoughts:

The criterion for good science is how good all the other scientists
think it is. If you produce a successful simplification of a model,
then it is possible to describe more complicated systems with it, and
that will promptly be done. The level of complexity is limited to what
the human brain can cope with; but in science, we always try to push
our brains to the limit (or at least, we should try to do so). If a
problem gets less complicated, we quickly finish it off and go for
something bigger ... and then things are just as complex as they used to be.

All the best,

               Ole Swang

--------------------------------------------------------------------------------

Rene Fournier writes  (<[email-masked]>

Subject: Law of conservation of difficulty: violations.

    On the same humoristic tone ...

    (I am citing the graph from memory from a very interesting
lecture by P. O. Lowdin; my apologies for possible misrepresentation
of his good words).

   I think there are important violations of the "law of conservation
of difficulty".  This happens when someone has a powerful intuition
about how to solve a problem.  Here is a humoristic illustration of
this.  The graph below pretends to show the error measured relative
to experiment as a function of the level of theory.  Contrary to
expectation, accuracy does not improve monotonously with increasing
sophistication of the theory: the graph is reminiscent of the radial
part of a 3s function, not a 1s.  The 3 nodal (zero-error) regions are
where quantum chemists try to be.  If you have poor physical/chemical
intuition, or if you are obsessed with the fear of being largely in
error, you have to settle for hard work and mathematical wizardry and
painfully work your way down the x axis towards full CI calculations.
If you're clever, AND willing to take the risk of saying a few foolish
things from time to time, you can work in an intermediate region which
you might call "HF/6-31G" (or, nowadays, B3LYP//6-31G ?).  Only a
handful of geniuses can work at "Pauling's level" and still be right
most of the time.

    ^
    |
    |
    |
    x
    x
    x
    |x    (Beginning
 E  |x     /  graduate students)
 r  |x    /
 r  |x   /
 o  |x  /             (Experienced graduate students)
 r  | x                        \
    | x                         \
    | x                          \            (Postdocs)
    | x                           \               /         Really, REALLY tough
    |  x                           x  x          /         /  fully ab initio
    |  x     Pauling's level    x        x      /         /   calculation.
    |  x      of theory      x              x  /         /  (tenured profs)
    |  x    /              x                    x       /
    |   x  /             x                  |       x  /                  Full CI
    |   x /             x                   |--->        x                  /
   0|  |x |        |   x |                  |                  x           /
----|--|-x|--------|--x--|------------------|-----------------------------x-->
    |0 | x|        | x   |                  |            Level of theory;
    |     x         x                                  Computational effort
    |      x       x  \
    |       x     x    \
    |         x x     Hartree-Fock 6-31G
    |                  level of theory
    |

    Cheers,
             Rene.
 |---------------------------------|-----------------------------|
 | R. Fournier                     |  [email-masked]  |
 | University of Nevada  Las Vegas |  [email-masked]   |
 | Department of Physics           |                             |
 | 4505 Maryland Parkway           |  phone : (702) 895 1706     |
 | Las Vegas, NV 89154-4002 USA    |  FAX   : (702) 895 0804     |
 |---------------------------------|-----------------------------|

===========================================================================
===========================================================================
(End of summary)

==============================================================================
Georg Schreckenbach                      Tel: (Canada)-403-220 8204
Department of Chemistry                  FAX: (Canada)-403-289 9488
University of Calgary                    Email: [email-masked]
2500 University Drive N.W.,  Calgary,  Alberta,  Canada,  T2N 1N4
==============================================================================