Joint Penn-UDel Colloquium on the Nature of Computing

Ask the Delphic Plasmid!

Tom Head

Department of Mathematical Science, Binghamton University

Algorithmic problems frequently have the following pattern: A finite set S is specified. Relations are specified among the elements of S. It is asked whether one or more of the subsets of S consist of elements that are related in prescribed ways. If such subsets exist, further information may be requested, such as the size of the largest such subset or the size of the smallest such subset. Familiar problems having this pattern are: finding the largest independent subset of a graph, finding the smallest vertex cover of a graph, deciding whether a graph has a Hamiltonian cycle, and deciding whether a Boolean formula is satisfiable.

Wet lab procedures will be suggested for the solution of problems of this type. The special feature of these procedures is that they all begin with a test tube containing the same plasmid. We call this plasmid DEL, the Delphic Plasmid, since it answers all our questions.

Plans for the construction of BABY DEL will be discussed in detail.