(UPDATE: My statements in this blog entry about the Göös Orponen paper were based on an earlier draft, which was on an author’s web page, but was not the final, published version. I have updated the link to their paper, and struck out my statements that are not consistent with their final draft. In particular, the final version of their paper reads, “Ma & Lombardi show a certain derivative of the above optimization problem NP-hard in . However, to our knowledge, a proof of the NP-hardness of the PATS problem as stated above is lacking.” Please see the comment of Mika Göös below for more information.)
One of my research interests is the DNA self-assembly of multicolored shapes. Almost all DNA self-assembly literature — both theory and practice — has focused on the assembly of either 1-color or 2-color shapes. Nevertheless, if we think of the DNA assembly as a substrate, or scaffolding, upon which transistors or nanomachines are placed later, different colors can correspond to OR gates or NAND gates, or the “landing pads” of much more sophisticated objects. A while back, I did a literature search on the self-assembly of multicolored shapes, and I thought I “knew everything” that was currently in the literature. However, I was wrong. I recently discovered papers in the literature track of Computer Assisted Design of integrated circuits (a track I had never followed before, and clearly I will have to start), whose objective is to tackle DNA self-assembly of multicolored rectangles, an obviously related special case of “my” problem. I will discuss two of these papers in this blog entry.
The two papers, both by Xiaojun Ma and Fabrizio Lombardi of Northeastern University, are On the Computational Complexity of Tile Set Synthesis for DNA Self-Assembly, and Combinatorial Optimization Problem in Designing DNA Self-Assembly Tilesets. The second is much shorter, reads like an announcement of results, and appeared in a workshop. The first appeared in a journal and contains a full proof of an NP-completeness result. I had initially intended this blog entry to be a technical discussion of the NP-completeness result, which I find clever, and I think it defines a graph model of tilesets that might be useful in other settings. However, when I looked into the literature, I found things were a bit of a mess.
A subsequent paper by other authors incorrectly states that Ma and Lombardi proved something stronger than they actually did, and this error is understandable, because Ma and Lombardi changed the informal description of their theorem in between the workshop paper and the journal paper. (The workshop paper makes a stronger claim, which the journal proof does not support.) So the rest of this entry reads more like a detective story — or a he-said she-said dialogue (!) — than an exposition. It took me a couple days to separate claims from proofs, and I hope that, by writing this up, I will save other researchers some time.