*I. Title*
Approaching P=NP: Can Soap Bubbles Solve The Steiner Tree Problem In Polynomial Time?

*II. Problem Statement*
It is currently unknown whether complexity class P (decision problems solvable in polynomial time) = complexity class NP (decision problems verifiable in polynomial time). The Steiner Tree Problem and its variants are known to be NP-Complete (the class of NP problem least likely to be in P). In covering a surface, soap bubbles always act so as to minimize surface area, which satisfies the Steiner Tree problem. The scope of this project will be 

*III. Purpose and Justification*
The purpose of this project is to make headway on the P=NP problem, by producing a solution to the Steiner Tree Problem, which is shown to be NP-Complete, that operates in polynomial time to the size of the input.

This is a good topic for the Computer Systems Lab because it is a highly algorithm intensive project.

The project is a worthwhile endeavor because it has stumped computer scientists and mathematicians for over fifty years. If it is proven that P=NP, then numerous computationally difficult problems can be reduced to much easier problems. This has great implications for a wide range of applied and theoretical fields, including graph theory, set theory, scheduling theory, number theory, language theory, and logic. An example of how this could be applied is optimal and faster calculation of the traveling salesman problem, which could be useful for parcel delivery services. 

*IV. Scope*
This project will probably need to focus less on the mathematically complex derivations of fluid mechanics (Navier-Stokes, etc), and more on trial and error modeling of emergent phenomena. To discover the algorithms that govern the behavior of the fluids, mathematical analyses will be required but in far less depth than of that required for actually deriving the behaviors.

*V. Literature review*
Numerous papers have been published that directly assert either that P=NP or P!=NP, or provide ever-faster algorithms for known problems in NP. However, relatively few academically reviewed papers have been published that attempt to provide an algorithm for P=NP. Techniques ranging from complexity theory to meta-physical analyses have been employed, but so far no one has produced an accepted proof. I do not expect to solve the P=NP problem, but I do intend to build on the work of those (Bringsjord and Taylor) who have proposed an unusual strategy.

Some basic reading: 

http://www.exploratorium.edu/ronh/bubbles/bubble_meets_bubble.html
http://www.newton.dep.anl.gov/askasci/gen01/gen01058.htm
http://web.mit.edu/1.63/www/Lec-notes/Surfacetension/
http://www.navier-stokes.net/
http://arxiv.org/abs/cs/0406056
http://www.win.tue.nl/~gwoegi/P-versus-NP.htm
http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP
http://en.wikipedia.org/wiki/Emergence
http://www.santafe.edu/~vince/emergence_alife/emergence_alife.html
http://arxiv.org/PS_cache/cs/pdf/0406/0406056.pdf

*VI. Procedure and Methodology*
Plan:
1. Research emergent phenomena and fluid dynamics.
2. Investigate fluid physics modeling tools. If none are available/appropriate, learn NetLogo, repast, and possibly avida.
3. Design an accurate model of the liquid behavior.
4. Implement this model in the software.
5. If time permits, reduce this implementation to an algorithm.

Materials:
1. Netlogo
2. repast
3. avida
4. Fluid dynamics textbook
5. Multivariable calculus textbook

For visual debugging, I will use Netlogo. A number of graphs whose total Steiner tree weights are already known will need to be generated. This is can easily be accomplished with C and will greatly aid correctness of the model.

*VII. Expected Results*
As previously stated, I do not *expect* to invent an algorithm that solves the Steiner Tree problem in polynomial time. I do expect to implement a correct software model and reduce this to a novel algorithm that solves the Steiner Tree problem, though probably not in polynomial time.

The final results, along with asymptotic run times and visual debugging charts, will be presented in a paper, on a poster, and also in a Powerpoint presentation.

This project will lay the foundation for the physics modeling approach to solve the P=NP problem and will require the nearly the entire academic year to reach completion. Most likely, a task chart will be used to record and monitor progress.