AF: Small: Verification Complexities of Self-Assembly Systems

自组装是小的、无组织的部件聚集在一起形成复杂结构的自然过程。一些系统，如DNA自组装，在自组装过程中足够强大，可以模拟通用计算。这种“算法自组装”是生物体功能的基础。此外，理解和利用算法自组装系统的力量有望实现对物质的算法操纵，也就是说，能够以类似于计算机编程的方式在纳米尺度上重新排列物质。因此，对算法自组装的坚实理论理解对未来的纳米技术至关重要。为了实现这一目标，该项目侧重于在一些实验驱动模型下“验证”自组装系统正确性的具体问题。通过设计有效验证的算法，或对此类问题的复杂性进行分类，该项目将为理解算法自组装和构建技术提供重要的理论基础，这将是推进该领域发展的关键。详细地说，这个项目集中在一些自组装模型上，这些自组装模型被广泛地分解为要么是“被动的”，其中系统组件基于静态表面化学吸引或排斥，要么是“主动的”，其中系统组件基于相互作用动态改变状态。该项目进一步根据系统是“几何”（利用形状来允许或防止组件之间的连接）还是“非几何”（组合仅基于键合域）对模型进行分类。不同的模型代表了常见的实现技术，如DNA附着、分子键合，甚至是实验室程序，如混合和分期反应。在这些类别中，要考虑特定的验证问题，例如“唯一组装验证”，其中的问题是确定给定系统是否唯一地组装到目标组装中，以及“可达性”，它询问给定系统是否有可能达到某个状态或配置。为了解决这些问题，项目研究人员将在考虑的模型中应用他们之前的专业知识，以及他们在相关工具方面的专业知识，例如“隐蔽计算”，这是一种由研究人员引入的加密工具，已被证明有效地解决了与自组装验证相关的长期开放问题。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Self-assembly is the natural process of small, unorganized components coming together to form complex structures. Some systems, such as DNA self-assembly, are powerful enough to simulate general-purpose computation during the self-assembly process. This type of "Algorithmic Self-Assembly" is fundamental to the functioning of living organisms. Moreover, understanding and harnessing the power of algorithmic self-assembly systems promises to allow for the algorithmic manipulation of matter, i.e., the ability to rearrange matter at the nanoscale in a fashion similar to the way a computer is programmed. Thus, a solid theoretical understanding of algorithmic self-assembly is fundamentally important for future nanotechnologies. Towards this goal, this project focuses on specific problems related to "verifying" the correctness of self-assembly systems under a number of experimentally motivated models. By designing algorithms for efficient verification, or categorizing the complexity of such problems, this project will provide important theoretical foundations for understanding algorithmic self-assembly and construction techniques that will be key to advancing the state of the field.In detail, this project focuses on a number of self-assembly models broadly broken up as being either "passive," in which system components attract or repel based on static surface chemistry, or "active" in which system components dynamically change state based on interactions. The project further classifies models based on whether a system is "geometric" (utilizing shape to allow or prevent attachment between components) or "non-geometric" (combination is based solely on bonding domains). The different models represent common implementation techniques such as DNA attachments, molecule bonding, or even laboratory procedures such as mixing and staging reactions. Within the categories, specific verification problems are considered, such as "Unique Assembly Verification" in which the problem is to determine if a given system uniquely assembles into a target assembly, and "Reachability," which asks if it is possible for a given system to reach a certain state or configuration. To solve these problems, the project investigators will apply their prior expertise within the models considered, as well as their expertise in relevant tools such as "Covert Computation," a cryptographic tool introduced by the investigators that has proven effective in resolving long-standing open problems related to verification in self-assembly.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.