License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SAND.2022.8
URN: urn:nbn:de:0030-drops-159503
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15950/
Go to the corresponding LIPIcs Volume Portal

Caballero, David ; Gomez, Timothy ; Schweller, Robert ; Wylie, Tim

Complexity of Verification in Self-Assembly with Prebuilt Assemblies

pdf-format:
LIPIcs-SAND-2022-8.pdf (1 MB)

Abstract

We analyze the complexity of two fundamental verification problems within a generalization of the two-handed tile self-assembly model (2HAM) where initial system assemblies are not restricted to be singleton tiles, but may be larger pre-built assemblies. Within this model we consider the producibility problem, which asks if a given tile system builds, or produces, a given assembly, and the unique assembly verification (UAV) problem, which asks if a given system uniquely produces a given assembly. We show that producibility is NP-complete and UAV is coNP^{NP}-complete even when the initial assembly size and temperature threshold are both bounded by a constant. This is in stark contrast to results in the standard model with singleton input tiles where producibility is in P and UAV is in coNP for ?(1) bounded temperature and coNP-complete when temperature is part of the input. We further provide preliminary results for producibility and UAV in the case of 1-dimensional linear assemblies with pre-built assemblies, and provide polynomial time solutions.

BibTeX - Entry

@InProceedings{caballero_et_al:LIPIcs.SAND.2022.8,
  author =	{Caballero, David and Gomez, Timothy and Schweller, Robert and Wylie, Tim},
  title =	{{Complexity of Verification in Self-Assembly with Prebuilt Assemblies}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15950},
  URN =		{urn:nbn:de:0030-drops-159503},
  doi =		{10.4230/LIPIcs.SAND.2022.8},
  annote =	{Keywords: 2-handed assembly, verification, prebuilt}
}

Keywords: 2-handed assembly, verification, prebuilt
Collection: 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Issue Date: 2022
Date of publication: 29.04.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI