Improving efficiency of 3-SAT-solving tile systems

DOI10.1007/978-3-642-18305-8_1MaRDI QIDQ3070958zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Efficient 3-SAT algorithms in the tile assembly model
• Solving satisfiability in the tile assembly model with a constant-size tileset
• Constant-Size Tileset for Solving an NP-Complete Problem in Nondeterministic Linear Time
• Solving NP-complete problems in the tile assembly model
• Solving vertex cover problem using DNA tile assembly model

Cites work

• Arithmetic computation in the tile assembly model: addition and multiplication
• Complexity of Self‐Assembled Shapes
• 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 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
• 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
• The program-size complexity of self-assembled squares (extended abstract)

Cited in

(4)

• Solving vertex cover problem using DNA tile assembly model
• Efficient 3-SAT algorithms in the tile assembly model
• Solving satisfiability in the tile assembly model with a constant-size tileset
• Constant-Size Tileset for Solving an NP-Complete Problem in Nondeterministic Linear Time

This page was built for publication: Improving efficiency of 3-SAT-solving tile systems

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