论文标题
在3D中非合作的薄矩形的独特自我组装的瓷砖复杂性上的上限和上限提高了上限
Improved lower and upper bounds on the tile complexity of uniquely self-assembling a thin rectangle non-cooperatively in 3D
论文作者
论文摘要
我们研究了关于最简单但最广泛使用的算法瓷砖自组装抽象模型之一中基于基准形状的基本问题。具体而言，我们研究了Winfree的抽象瓷砖组装模型中A $ k \ times n $薄矩形的定向瓷砖复杂性，假设不能强制执行合作绑定（温度1自组装），并且可以将瓷砖放入最多的一步进入第三维度（仅3D）。虽然正方形的定向瓷砖复杂性和在温度1处的任何算法的规定形状的缩放版本均与（分别是3D）均与（分别在2D温度2D中的）渐近，但在2D中的定向瓷砖复杂性在温度2中的定向瓷砖复杂性在2D中的定向瓷砖复杂性在2D中均未在2D中均未在温度下达到仅在温度下的1 in of Pertive 1 in Perver 1 in Bargy 1 in Barne Bains 3d。在这种差异的驱动下，我们在温度1的薄矩形的定向瓷砖复杂性上建立了新的下层和上限，以3D的速度为1。我们开发了一种新型，更强大的窗口电影引理类型，使我们能够限制“足够相似”方法的数量，以将胶水分配到一组固定位置。因此，我们的下限，$ω\ left（n^{\ frac {1} {k}} \ right）$是对以前最佳下限的渐近改进，并且在美观上更令人愉悦，因为它消除了用于除以$ n^{\ frac {\ frac {\ frac {1}} $的$ k $。我们上限的证明是基于根据“数字区域”组织的恰好是3D，温度-1计数器，与以前的最佳计数器相比，同一目标矩形的数字可为同一目标矩形的数字增加约50％。数字密度的这种增加导致$ o \ left的上限（n^{\ frac {1} {\ left \ lfloor \ frac {k} {2} {2} \ right \ rfloor}}+rfloor}}+\ log n \ right \ right）$，这是一个比以前的最佳界限和较低的方形，这是一个差异的范围。
We investigate a fundamental question regarding a benchmark class of shapes in one of the simplest, yet most widely utilized abstract models of algorithmic tile self-assembly. Specifically, we study the directed tile complexity of a $k \times N$ thin rectangle in Winfree's abstract Tile Assembly Model, assuming that cooperative binding cannot be enforced (temperature-1 self-assembly) and that tiles are allowed to be placed at most one step into the third dimension (just-barely 3D). While the directed tile complexities of a square and a scaled-up version of any algorithmically specified shape at temperature 1 in just-barely 3D are both asymptotically the same as they are (respectively) at temperature 2 in 2D, the bounds on the directed tile complexity of a thin rectangle at temperature 2 in 2D are not known to hold at temperature 1 in just-barely 3D. Motivated by this discrepancy, we establish new lower and upper bounds on the directed tile complexity of a thin rectangle at temperature 1 in just-barely 3D. We develop a new, more powerful type of Window Movie Lemma that lets us upper bound the number of "sufficiently similar" ways to assign glues to a set of fixed locations. Consequently, our lower bound, $Ω\left(N^{\frac{1}{k}}\right)$, is an asymptotic improvement over the previous best lower bound and is more aesthetically pleasing since it eliminates the $k$ that used to divide $N^{\frac{1}{k}}$. The proof of our upper bound is based on a just-barely 3D, temperature-1 counter, organized according to "digit regions", which affords it roughly fifty percent more digits for the same target rectangle compared to the previous best counter. This increase in digit density results in an upper bound of $O\left(N^{\frac{1}{\left\lfloor\frac{k}{2}\right\rfloor}}+\log N\right)$, that is an asymptotic improvement over the previous best upper bound and roughly the square of our lower bound.
