Efficient 3-SAT algorithms in the tile assembly model

DOI10.1007/S11047-011-9299-0MaRDI QIDQ2629931zbMATH OpenOpenAlexFDO

Authors Yuriy Brun

Publication date 8 July 2016

Published in Natural Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11047-011-9299-0

zbMATH Keywords

3-SATefficient 3-SAT algorithmsself-assemblytile-assembly model

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Improving efficiency of 3-SAT-solving tile systems
• Solving satisfiability in the tile assembly model with a constant-size tileset
• Solving NP-complete problems in the tile assembly model
• Constant-Size Tileset for Solving an NP-Complete Problem in Nondeterministic Linear Time
• scientific article; zbMATH DE number 1568805

Cites work

• Arithmetic computation in the tile assembly model: addition and multiplication
• Complexities for Generalized Models of Self-Assembly
• Complexity of Self‐Assembled Shapes
• DNA Computing
• Error suppression mechanisms for DNA tile self-assembly and their simulation
• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 1241374 (Why is no real title available?)
• scientific article; zbMATH DE number 515744 (Why is no real title available?)
• scientific article; zbMATH DE number 1113996 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• scientific article; zbMATH DE number 1738648 (Why is no real title available?)
• scientific article; zbMATH DE number 1568805 (Why is no real title available?)
• New methods for 3-SAT decision and worst-case analysis
• Nondeterministic polynomial time factoring in the tile assembly model
• Path finding in the tile assembly model
• Reducing tile complexity for self-assembly through temperature programming
• Solving NP-complete problems in the tile assembly model
• Solving satisfiability in less than \(2^ n\) steps
• Solving satisfiability in the tile assembly model with a constant-size tileset
• Staged Self-assembly: Nanomanufacture of Arbitrary Shapes with O(1) Glues
• The program-size complexity of self-assembled squares (extended abstract)
• Undecidability and nonperiodicity for tilings of the plane

Cited in

(6)

• Improving efficiency of 3-SAT-solving tile systems
• Solving satisfiability in the tile assembly model with a constant-size tileset
• scientific article; zbMATH DE number 1568805 (Why is no real title available?)
• A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis
• Constant-Size Tileset for Solving an NP-Complete Problem in Nondeterministic Linear Time
• Solving NP-complete problems in the tile assembly model

This page was built for publication: Efficient 3-SAT algorithms in the tile assembly model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2629931)