October 15, 2021

About the speaker

Timothy Gomez is a graduate student in the department of computer science at UTRGV. He received the Presidential Graduate Research Assistantship during his masters.

Additional authors for this work include: David Caballero, Timothy Gomez, Robert Schweller and Tim Wylie

The Complexity of Multiple Handed Self-Assembly

In this paper we study complexities for the multiple-handed tile self-assembly model, a generalization of the two-handed tile assembly model in which assembly proceeds by repeatedly combining up to h assemblies together into larger assemblies. We first show that there exist shapes that are self-assembled with provably lower tile type complexities given more hands: we construct a class of shapes Sk that requires Ω( k h ) tile types to self-assemble with h or fewer hands, and yet is self-assembled in O(1) tile types with k hands. We further examine the complexity of self-assembling the classic benchmark n × n square shape, and show how this is self-assembled in O(1) tile types with O(n) hands. We next explore the complexity of established verification problems. We show the problem of determining if a given assembly is produced by a h-handed system is polynomial time solvable, whereas the problem of unique assembly verification is coNP-complete if the hand parameter h is encoded in unary, and coNEXP-complete if h is encoded in binary.