David H. Wood
Department of Computer Science, University of Delaware

DNA model of matching with variable costs (c) (Graphic by John Furno)

Suppose N renters, with their security deposits, are to be matched with mutually compatible landlords. One interesting aspect of this problem is that the formal complexity (as N grows large) varies greatly with the question you ask.

Question	Complexity
Is there some way to match everyone?	Easy (Polynomial)
If so, what is the minimum budget for rental deposits?	Easy (Polynomial)
Show a few of the ways to match everyone.	Easy (Polynomial)
Can everyone be matched using a prespecified budget?	Hard (NP-complete)
In how many ways can everyone be matched?	Very Hard (#P-complete)
Show all the ways everyone can be matched.	Very Very Hard

We present DNA algorithms for some of the hard problems. A notable remarkable aspect of these algorithm is that the error-prone operation of separation is not used. We present an analysis of complexity of these algorithms. If there are N renters, these algorithms use O(N) time steps during each of which O(N^2) operations are simultaneously carried out by reprogrammed laboratory robots. We give a way to estimate ahead of time how much DNA will be required. Since separation is never used, the algorithm can never construct any candidate solutions that are not actual solutions.

(This is joint work with T. H. Leete, M. D. Schwartz, R. M. Williams, J. S. Salem and H. Rubin.)

Friday, October 17 at 4pm in room Room 209 of the Johnson Pavilion near Spruce and 36th Streets on the University of Pennsylvania campus. Travel Directions are found at http://www.upenn.edu/fm/map/dir.html