RE: Uncertainty and Liquidity Preference

["Lisa & Ian Murray" <seamus@xxxxxxxxxxxxx>]

Nonlinearity is neither a necessary nor a sufficient condition for
> nonergodicity.  One should not confound one with the other.  Nonlinear
> systems can be ergodic and linear systems can be ergodic.




I wasn't implying that they were mutually implicative, apologies if the
grammar threw anyone off.  BTW, for an interesting aside that is of some
relevance to PKTer's regarding these issues, there is this article in
today's NYT.

Ian

July 13, 1999


Separating Insolvable and Difficult

----------------------------------------------------------------------------
----
Chart
Solving Problems
Forum

Join a Discussion on Science in the News
----------------------------------------------------------------------------
----

By GEORGE JOHNSON

nyone trying to cast a play or plan a social event has come face-to-face
with what scientists call a satisfiability problem. Suppose that a
theatrical director feels obligated to cast either his ingénue, Actress
Alvarez, or his nephew, Actor Cohen, in a production. But Miss Alvarez won't
be in a play with Cohen (her former lover), and she demands that the cast
include her new flame, Actor Davenport. The producer, with her own favors to
repay, insists that Actor Branislavsky have a part. But Branislavsky won't
be in any play with Miss Alvarez or Davenport.

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

Examining the secrets of computational complexity.

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


As more roles need to be filled, the problem becomes harder and harder to
solve. Is it possible to satisfy the tangled web of conflicting demands?
These satisfiability problems, called SAT problems for short, arise in
thousands of situations, from staffing companies and scheduling airline
flights to planning a wedding dinner that won't devolve into a food fight.

And, reaching beyond such practical considerations, researchers embrace
satisfiability problems as a tool for studying a phenomenon called
computational complexity: some problems are inherently easy to solve, some
difficult and some impossible, but scientists are only beginning to
understand why.

A paper in the current issue of Nature adds to a string of developments on
the topic that have emerged over the last few years. In it an international
team of physicists and computer scientists describes work that could help
weed out problems that are hopeless and suggest more efficient methods, or
algorithms, for solving the rest.

Most intriguingly, this and recent research from other laboratories may help
clarify a curious phenomenon that has puzzled scientists for years: the
existence of a kind of "phase transition" in which satisfiability problems
suddenly change from easy to hard as abruptly as water freezing into ice. A
deeper understanding of this parallel might allow physicists to apply ideas
about phase transitions occurring in nature to understanding complex
mathematical problems, and vice versa: the computer scientists might help
shed light on phenomena in the physical world.

"We hope we have finally found the right point of contact between physics
insights and computational complexity," said Scott Kirkpatrick of the I.B.M.
Thomas J. Watson Research Center in Yorktown Heights, N.Y., a co-author of
the most recent study, which also included Rémi Monasson of the
CNRS-Laboratoire de Physique Théorique in Paris; Riccardo Zecchina of the
Abdus Salam International Center for Theoretical Physics in Trieste, Italy;
Bart Selman of Cornell University, and Lidror Troyansky of Hebrew University
in Jerusalem.

"This connection between such seemingly different fields is likely to shed
light on both," said Tad Hogg of the Xerox Palo Alto Research Center in
California, who has done pioneering work in this area with his colleague
Bernardo Huberman.

"Practically, it may lead to better search algorithms for typical problems,
though that remains to be seen."

In computer science, problems can be rated in difficulty by how much time it
takes to search for solutions. If there are just a few actors to cast in a
play, the answer can be found simply by trial and error.

For five actors, there are only 2 to the 5th possibilities, a mere 32
combinations: A is in, B is out, C is out, D is in, E is out.

The director can try every combination and see if any are consistent with
everyone's demands.

In practice, it is usually not necessary to "exhaustively search the problem
space," as mathematicians say. It is quickly evident that there is no way to
cast Miss Alvarez, but that the play can go forward with Cohen. For enormous
problems involving many variables, pursuing such shortcuts can often save
valuable computer time.

Viewed more abstractly, the casting example belongs to a class called 2-SAT
problems. If parsed into a logical formula (a kind of mathematical syntax
called "conjunctive normal form"), they contain so-called clauses like
"Alvarez or Cohen," which each involve no more than two of the potential
actors. If one tries to cast a play with 10 or 100 actors, the problem
becomes harder. But as long as there are no more than two variables, or
actors, in each of the many clauses, the solution time increases relatively
slowly, in what is called polynomial time. Thus 2-SAT problems are said
belong to a class of solvable problems called P.

But in more complex situations, with clauses that each have at least three
variables ("Alvarez or Branislavsky or Cohen"), the space of possible
solutions to explore can explode exponentially as the problem grows larger,
with more actors added to the play. In the worst cases, these 3-SAT
problems -- even ones with only 50 actors -- rapidly become unsolvable, even
given eons of time. This places them in the domain of difficult problems
called NP-complete. You can guess at the answer and quickly determine if
it's right or wrong (by coming up with a combination of actors and seeing if
it works.) But systematically solving the problem can essentially take
forever.

The initials NP stand for the rather opaque term "nondeterministic
polynomial." The important point is that all NP-complete problems are
intimately related. Other examples include the famous traveling salesman
problem, in which you try to find the shortest route connecting many
different cities. As the number of destinations increases, the difficulty
can rise exponentially and even good approximations are a challenge. If a
mathematician could find a general means of solving satisfiability problems
this would also dispose of the traveling salesman problem and thousands of
others.

But mathematicians strongly suspect that unless they have been missing
something, there is no general way to solve large NP-complete problems
precisely during the lifetime of the human race or even the universe.
Instead, researchers look for ways to understand which problems are merely
difficult and which are impossibly complex.

If all 2-SAT problems were solvable and all 3-SAT problems were not, life
would be easy -- just don't bother with 3-SAT's. But the situation is not so
clear-cut. A class of problems is relegated to NP-complete if even a single
case is intractable. Though the constraints involved in casting one play
might cause the problem to grow so rapidly in complexity that no computer
could solve it, a seemingly similar play might be cast with relative ease.
The challenge is to find a way to separate the two.

Computer scientists start by randomly generating a pool of SAT problems each
involving different actors and different casting constraints. (Or the
variables might be thought of as airplanes, and the constraints as the
routes they must fly.) Then each problem is located as a dot on a graph. A
variable called alpha (the ratio of the number of clauses, or demands, to
the number of actors) runs along the horizontal axis and a measure of the
difficulty of solving the problem on the vertical axis. Then scientists
study the way the problems cluster into patterns.

On the surface, the outcome is easily predictable: If the alpha ratio is
low, there are only a few demands to satisfy and a large supply of actors to
draw on. Solutions tend to be plentiful. If, on the other hand, the ratio of
demands to available actors is high enough, mutually agreeable solutions are
probably impossible.

The surprise comes from looking deeper: One might expect that the transition
from easy to unsolvable would be gradual.

But there is an abrupt transition analogous to water freezing into ice as
the thermometer drops from 33 to 32 degrees Fahrenheit. A tiny increase in
the parameter called alpha causes the problems to suddenly become very hard.

And studies have shown an even more intriguing pattern.

The easy problems to the left of the divide can obviously be solved quickly.
This is also true for the problems on the other side of the divide: It
usually becomes quickly evident that they are impossible and can be
abandoned. It is the barely solvable problems lying in the region in
between -- in the zone of the so-called phase transition -- that are the
most time-consuming. They are hard but not obviously futile.

Whether one is seeking the most efficient paths for the circuitry on a
computer chip or scheduling airplanes, it is in this nether region where the
most tantalizing problems lie.

"That's why there is such strong interest in what happens at this phase
transition," said Dr. Selman, one of the authors of the Nature report. "It's
where a lot of real problems are going to be."

For a while, some computer scientists held out hope that all problems that
showed a phase transition could automatically be banished to the class
called NP-complete. But the situation has turned out to be more subtle. Some
easier problems like the 2-SAT variety also undergo phase transitions. But
it's recently become clearer that for 2-SAT problems the transition from
soluble to insoluble is relatively smooth, while with 3-SAT problems it is
abrupt.

The study published last week goes further. After studying random pools of
formulas that mix 2- and 3-actor clauses, the authors conjecture that, in
general, simple P problems will have smooth transitions, while NP-complete
problems will have abrupt transitions. If this can be more rigorously shown,
a breakthrough may be at hand.

Most interesting of all, the authors suggest why the abrupt transitions
occur. Scientists often study complex systems by comparing them with an
idealized substance (simulated on a computer) called a spin glass. These
alloys contain a random distribution of magnetic particles that, roughly
speaking, can point up or down. Think of each particle as one of the actors
whose demands must be met. "Up" means in the play, "down" means out. Just as
the presence or absence of an actor can affect whether others remain in the
cast, the orientation of a magnetic particle can affect the way its
neighbors line up. Solving a satisfiability problem becomes equivalent to
getting the spin glass to settle down into a state with all the particles
comfortably coexisting.

The authors suggest that whether one is looking at SAT problems or spin
glasses, abrupt phase transitions are caused by the formation of a
"backbone" of particles (or actors) that are permanently frozen into one
state or the other (like Miss Alvarez refusing to act with Cohen).
Understanding the formation of these structures could lead to new
problem-solving techniques for both physicists and computer scientists.

In the past, the flow of information between these two fields has been
largely one-way, to the benefit of the computer scientists. Dr. Selman hopes
some of his group's insights will flow back the other way, deepening the
understanding of the physical world. "It's a sign," he said, "of computer
science becoming more mature."

http://www.nytimes.com/library/national/science/071399sci-satisfiability-pro
blems.html





> -----Original Message-----
> From: owner-pkt@xxxxxxxxxxxxxxxx [mailto:owner-pkt@xxxxxxxxxxxxxxxx]On
> Behalf Of Paul Davidson
> Sent: Tuesday, July 13, 1999 8:32 AM
> To: POST-KEYNESIAN THOUGHT
> Subject: RE: Uncertainty and Liquidity Preference
>
>
> At 09:53 PM 7/12/99 -0700, you wrote:
> >Doesn't this bias our sense of uncertainty towards merely sorites paradox
> >types of ignorance.  Surely our problems of uncertainty are greater than
> >mere additivity?  if the economic world is non-linear and
> non-ergodic, then
> >surely our theory of ignorance, and error correction (improving
> predictive
> >capacity) as well as errors in tracking it (the economy) must be
> non-linear
> >as well?
> >
> >Ian
> >
>
> Nonlinearity is neither a necessary nor a sufficient condition for
> nonergodicity.  One should not confound one with the other.  Nonlinear
> systems can be ergodic and linear systems can be ergodic.
> Paul Davidson
> Holly Chair of Excellence in Political Economy
> Editor, JOURNAL OF POST KEYNESIAN ECONOMICS [JPKE]
> Economics Department -- 523 SMC
> University of Tennessee
> Knoxville, Tennessee 37996-0550
> email: Pdavidson@xxxxxxx;   phone: (423)974-4221;    fax: (423) 974-4601
> http://econ.bus.utk.edu/Davidson.html
>