We analyze the computational complexity of basic reconfiguration problems for the recently introduced surface Chemical Reaction Networks (sCRNs), where ordered pairs of adjacent species nondeterministically transform into a different ordered pair of species according to a predefined set of allowed transition rules (chemical reactions). In particular, two questions that are fundamental to the simulation of sCRNs are whether a given configuration of molecules can ever transform into another given configuration, and whether a given cell can ever contain a given species, given a set of transition rules. We show that these problems can be solved in polynomial time, are NP-complete, or are PSPACE-complete in a variety of different settings, including when adjacent species just swap instead of arbitrary transformation (swap sCRNs), and when cells can change species a limited number of times (k-burnout). Most problems turn out to be at least NP-hard except with very few distinct species (2 or 3).
翻译:我们分析了最近引入的表面化学反应网络(sCRNs)中基本重构问题的计算复杂性,其中有序的相邻物种根据预定义的允许转换规则(化学反应)被非确定性地转化为不同的有序物种对。特别地,关于sCRNs模拟的两个基本问题是,是否可以将给定的分子构型转化为另一个给定的构型,以及是否可以在给定的转换规则下包含给定的物种。我们展示了这些问题可以在不同的设置中通过多项式时间,NP完全或PSPACE完全解决,包括相邻物种只交换而不是进行任意转化(swap sCRNs)时,以及当细胞可以有限次改变物种时(k-burnout)。除非物种非常少(2或3),否则大多数问题都至少是NP困难的。