2026-07-23T03:28:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14604 2024-03-06T10:54:25Z ddc:004 open_access

Covert Computation in Staged Self-Assembly: Verification Is PSPACE-Complete Caballero, David Gomez, Timothy Schweller, Robert Wylie, Tim self-assembly covert computation staged self-assembly assembly verification 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David Caballero and Timothy Gomez and Robert Schweller and Tim Wylie 2021 Is Part Of LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2021.23 urn:nbn:de:0030-drops-146047 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.23 eng https://creativecommons.org/licenses/by/4.0/legalcode