Transcript Approaching P=NP: Can Soap Bubbles Solve The Steiner Tree

Approaching P=NP: Can Soap
Bubbles Solve The Steiner Tree
Problem In Polynomial Time?
Long Ouyang
Computer systems
Introduction
• Decision problems – Ask yes/no
questions.
• Two classes of problems, P and NP
– P: Problems that can be solved in time
polynomial to the size of the input by a
deterministic Turing machine.
– NP: Problems that can be solved in time
polynomial to the size of the input by a
nondeterministic Turing machine.
Turing machines (not important)
Deterministic:
-At most one entry
for each
combination of
symbol and state.
Non-deterministic:
-More than one
entry for each
combination of
symbol and state.
What does this mean?
• With regards to modern computers:
– Problems in P can be solved in polynomial
time.
– Solutions to problems in NP can be verified in
polynomial time.
• Problems in P take relatively less time to
solve, problems in NP take relatively more.
NP
• Problems in NP:
– Traveling salesman problem
– Hamiltonian path problem
– Partition problem
– Multiprocessor scheduling
– Bin packing
– Sudoku
– Tetris
Who cares?
• If P=NP, hard problems are actually
relatively easy.
– Implications: Cryptography, Mapquest,
compression, scheduling, computation
How?
• Try to devise P algorithms to NP-Complete
problems.
– Problem: Turing arguments, Razborov-Rudich
barrier
So what do we do?
• Physical systems – often in nature,
physical systems reduce a situation to its
lowest energy state (optimizing energy).
– Soap films
– Spin glasses
– Folding proteins
– Bubbles
Additional methods
• Quantum computing
• Using DNA as non-deterministic Turing
machines.
• Time travel
• Quantum computing
• Anthropic principles
We’ll take the soap, please
• Pros:
– It’s inexpensive, compared to time travel.
– Reduces P=NP to a problem in digital
physics.
• Cons:
– Makes formal proof at the least, very difficult
– Optimistically, at best, provides experimental
run-time data
The Steiner Problem
Soap is rumored to solve the Steiner Tree
Problem (STP).
Steiner Tree Problem:
Description: Given a weighted graph G, G(V,E,w), where V is the set of vertices,
E is the set of edges, and w is the set of weights, and S, a subset of V, find the
subset of G that contains S and has the minimum weight.
Find the minimum spanning tree
for a bunch of vertices, given that you
can add additional points.
Simply put:
How does soap do this?
• Soap, in water, acts as a surfactant, which
decreases the surface tension of the
water.
• This acts to minimize the surface energy
of the liquid.
• This should minimize surface area (graph
weight), and solve the problem.
Tools used
• OpenFOAM (computational fluid physics
engine)
• Paraview (visualization engine)
• GeoSteiner '96 (exact STP solver)
Design
• Generation of random vertices,
appropriate mesh for OpenFOAM
• Solution of STP (where nodes are the
random vertices) by GeoSteiner '96
• OpenFOAM computation of soap action on
vertices
• Comparison of exact solution with soap
solution
Soap model
• Thin box filled with soap water.
• Pegs connect the same parallel faces of the
box (nodes)
• There's a small drain at the bottom of the
box.
Ideal soap solution
Conclusions
• Agent-based modeling sucks for modeling
fluids.
• Rigid-body physics sucks for modeling
fluids.