based on, in 2006. Three years later, they published a paper in Science, describing how Eureqa took measurements of the complex motions of a double pendulum and used the evolutionary process to derive Hamiltonian and Lagrangian differential equations that describe the laws of motion.

Lipson’s hope is that this approach
can expand human capabilities in sci-
ence. “In classical experimentation,
you vary one parameter at a time,” he
says. A computer can alter all the pa-
rameters at once to find the best ex-
periment. “If you have 18 variables,
there’s no way you can conceptualize
that, but the machine can.”
The research does not knock hu-
mans out of scientific discovery. “The
expectation would be that you find
the model fast, and you are able to
look deeper into your data,” Lipson
says. “In the end, you do have to have
an expert to look at these equations
and ponder their meaning and decide
whether they’re actually useful.”

 

Robots as Principal investigator Increasingly, scientists are enlisting the help of robots, such as the ones used in high-throughput drug discovery, to manipulate materials and gather data. “The concept is to try to automate the cycle of scientific research, which involves forming hypotheses and being able to test them,” says Ross King, who headed the computational biology group at Aberystwyth University but recently moved to the Manchester Interdisciplinary Biocenter at the University of Manchester where he is a professor of machine intelligence. He

Why not enlist
a robot to
generate data,
form a hypothesis,
and design
experiments to
test its hypothesis?

used a robotic system he calls Adam to run biological experiments on microtiter plates that hold miniscule amounts of samples, and can run several different experiments within millimeters of each other. Adam compared growth rates of natural yeast cells with a series of genetically altered cells, each of which was missing a different gene, and was able to identify the function of different genes.

King says robots have already surpassed humans’ capabilities in the physical aspects of the experiment, such as the placement of different yeast strains in miniscule holes on the microtiter plates. So why not have a robot conduct the entire experiment—generate data, form a hypothesis, design new experiments to test the hypothesis, and then work with the new data?

The system is not quite that ad-
vanced yet, King admits. “I don’t think
Adam is capable of generating a hy-
pothesis that is cleverer than what a
human could do,” he says. “I think in
maybe 20 years there will be robots
able to do almost any experiment in
the wet biology lab.”
“We’re a long way from automating
the entire scientific enterprise,” says
Patrick Langley, head of the Cogni-
tive Systems Laboratory at Stanford
University. Langley has argued for the
validity of computational discovery
since the early 1980s, when he and
the late Herbert Simon, a pioneer
in artificial intelligence, first wrote
about an early scientific discovery
program called BACON. The work by
Lipson and King, he says, is well with-
in that tradition.

Theory

P vs. NP Poll Results

Does P = NP Not according to
the great majority of computer
scientists who responded to the
latest opinion poll conducted
by William Gasarch, professor
of computer science at the
University of Maryland, College
Park. Gasarch recently polled
150 researchers about the
largest unsolved problem in
computer science, and found
that 81% do not believe P =
NP. In 2002, Gasarch polled

100 researchers on the P vs. NP problem, and found that 61% did not believe P = NP, 9% believed P = NP, and 30% said they did not know or the problem was unsolvable.

Increasingly, researchers do not believe P vs. NP will be solved anytime soon. In the 2002 poll, 62% of the respondents said an answer would appear before 2100. In the latest poll, the number of

respondents who believe so has shrunk to 53%.

“even though the percentage
of people who think it will be
solved before 2100 has gone
down, I am still surprised it
is as high as it is,” Gasarch
said in an email interview.
“People’s optimism about the
problem surprises me and is
significant.”
Gasarch believes a proof
will take 200–400 years.

“My opinion, and frankly
anyone’s opinion, is really a
guess. Having said that, my
impression is that we are really
at a standstill. There has been
no progress and there is no
real plan of attack. Geometric
complexity theory may be an
exception, but that will also take
a long time to prove anything.”
As for Gasarch, he does not
believe P = NP.