Improving Efficiency of 3-SAT-Solving Tile Systems

DOI10.1007/978-3-642-18305-8_1zbMath1309.68065OpenAlexW1504300383MaRDI QIDQ3070958

Yuriy Brun

Publication date: 28 January 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-18305-8_1

Mathematics Subject Classification ID

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

Cites Work

• Arithmetic computation in the tile assembly model: addition and multiplication
• Nondeterministic polynomial time factoring in the tile assembly model
• Solving NP-complete problems in the tile assembly model
• Solving satisfiability in less than \(2^ n\) steps
• New methods for 3-SAT decision and worst-case analysis
• The program-size complexity of self-assembled squares (extended abstract)
• Solving satisfiability in the tile assembly model with a constant-size tileset
• Complexity of Self‐Assembled Shapes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Improving Efficiency of 3-SAT-Solving Tile Systems