Constant-Size Tileset for Solving an NP-Complete Problem in Nondeterministic Linear Time

DOI10.1007/978-3-540-77962-9_3MaRDI QIDQ5452688zbMATH OpenOpenAlexFDO

Authors Yuriy Brun

Publication date 4 April 2008

Published in DNA Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77962-9_3

Mathematics Subject Classification ID

Tilings in (2) dimensions (aspects of discrete geometry) (52C20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Solving NP-complete problems in the tile assembly model
• Solving satisfiability in the tile assembly model with a constant-size tileset
• Nondeterministic polynomial time factoring in the tile assembly model
• Efficient 3-SAT algorithms in the tile assembly model
• Improving efficiency of 3-SAT-solving tile systems

Cited in

(8)

• Solving vertex cover problem using DNA tile assembly model
• Efficient 3-SAT algorithms in the tile assembly model
• Improving efficiency of 3-SAT-solving tile systems
• An efficient tile assembly model for maximum matching problem
• Solving satisfiability in the tile assembly model with a constant-size tileset
• scientific article; zbMATH DE number 1460255 (Why is no real title available?)
• Nondeterministic polynomial time factoring in the tile assembly model
• Solving NP-complete problems in the tile assembly model

This page was built for publication: Constant-Size Tileset for Solving an NP-Complete Problem in Nondeterministic Linear Time

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