AF: Small: Verification Complexities of Self-Assembly Systems

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

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.