AF: Small: Verification Complexities of Self-Assembly Systems

AF：小：自组装系统的验证复杂性

• 批准号: 2329918
• 负责人: Tim Wylie
• 金额: $ 60万
• 依托单位: The University of Texas Rio Grande Valley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-01-15 至 2026-12-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2329918&HistoricalAwards=false
• 关键词: AF; Small; Verification; Complexities; Self

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.

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