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.ESA.2021.23
URN: urn:nbn:de:0030-drops-146047
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14604/
Caballero, David ;
Gomez, Timothy ;
Schweller, Robert ;
Wylie, Tim
Covert Computation in Staged Self-Assembly: Verification Is PSPACE-Complete
Abstract
Staged self-assembly has proven to be a powerful abstract model of self-assembly by modeling laboratory techniques where several nanoscale systems are allowed to assemble separately and then be mixed at a later stage. A fundamental problem in self-assembly is Unique Assembly Verification (UAV), which asks whether a single final assembly is uniquely constructed. This has previously been shown to be Π^{p}₂-hard in staged self-assembly with a constant number of stages, but a more precise complexity classification was left open related to the polynomial hierarchy.
Covert Computation was recently introduced as a way to compute a function while hiding the input to that function for self-assembly systems. These Tile Assembly Computers (TACs), in a growth only negative aTAM system, can compute arbitrary circuits, which proves UAV is coNP-hard in that model. Here, we show that the staged assembly model is capable of covert computation using only 3 stages. We then utilize this construction to show UAV with only 3 stages is Π^{p}₂-hard. We then extend this technique to open problems and prove that general staged UAV is PSPACE-complete. Measuring the complexity of n stage UAV, we show Π^{p}_{n - 1}-hardness. We finish by showing a Π^{p}_{n + 1} algorithm to solve n stage UAV leaving only a constant gap between membership and hardness.
BibTeX - Entry
@InProceedings{caballero_et_al:LIPIcs.ESA.2021.23,
author = {Caballero, David and Gomez, Timothy and Schweller, Robert and Wylie, Tim},
title = {{Covert Computation in Staged Self-Assembly: Verification Is PSPACE-Complete}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {23:1--23:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-204-4},
ISSN = {1868-8969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14604},
URN = {urn:nbn:de:0030-drops-146047},
doi = {10.4230/LIPIcs.ESA.2021.23},
annote = {Keywords: self-assembly, covert computation, staged self-assembly, assembly verification}
}
Keywords: |
|
self-assembly, covert computation, staged self-assembly, assembly verification |
Collection: |
|
29th Annual European Symposium on Algorithms (ESA 2021) |
Issue Date: |
|
2021 |
Date of publication: |
|
31.08.2021 |