Flattening fixed-angle chains is strongly NP-hard
Pages 314 - 325
Abstract
Planar configurations of fixed-angle chains and trees are well studied in polymer science and molecular biology. We prove that it is strongly NP-hard to decide whether a polygonal chain with fixed edge lengths and angles has a planar configuration without crossings. In particular, flattening is NP-hard when all the edge lengths are equal, whereas a previous (weak) NP-hardness proof used lengths that differ in size by an exponential factor. Our NP-hardness result also holds for (nonequilateral) chains with angles in the range [60° - ε, 180°], whereas flattening is known to be always possible (and hence polynomially solvable) for equilateral chains with angles in the range (60°, 150°) and for general chains with angles in the range [90°, 180°]. We also show that the flattening problem is strongly NP-hard for equilateral fixed-angle trees, even when every angle is either 90° or 180°. Finally, we show that strong NP-hardness carries over to the previously studied problems of computing the minimum or maximum span (distance between endpoints) among non-crossing planar configurations.
References
[1]
Aloupis, G., Demaine, E.D., Vida, E.D., Erickson, J., Langerman, S., Meijer, H., O'Rourke, J., Overmars, M.H., Soss, M.A., Streinu, I., Toussaint, G.T.: Flat-state connectivity of linkages under dihedral motions. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol. 2518, pp. 369-380. Springer, Heidelberg (2002).
[2]
Aloupis, G., Meijer, H.: Reconfiguring planar dihedral chains. In: European Conference on Computational Geometry (March 2006).
[3]
de Berg, M., Khosravi, A.: Optimal binary space partitions in the plane. In: Thai, M.T., Sahni, S. (eds.) COCOON 2010. LNCS, vol. 6196, pp. 216-225. Springer, Heidelberg (2010).
[4]
Demaine, E.D., O'Rourke, J.: Fixed-Angle Linkages. Cambridge University Press, Cambridge (2007).
[5]
Gillespie, R.J., Popelier, P.L.A.: Molecular geometry and the vsepr model. In: Chemical Bonding and Molecular Geometry: From Lewis to Electron Densities, ch.4. Oxford University Press (2001).
[6]
Knuth, D.E., Raghunathan, A.: The problem of compatible representatives. SIAM J. Discrete Math. 5(3), 422-427 (1992).
[7]
Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329-343 (1982).
[8]
Soss, M.: Geometric and Computational Aspects of Molecular Reconfiguration. PhD thesis. School of Computer Science, McGill University (2001).
[9]
Soss, M., Toussaint, G.T.: Geometric and computational aspects of polymer reconfiguration. Journal of Mathematical Chemistry 27(4), 303-318 (2000).
- Flattening fixed-angle chains is strongly NP-hard
Recommendations
The complexity of constructing pseudorandom generators from hard functions
We study the complexity of constructing pseudorandom generators (PRGs) from hard functions, focussing on constant-depth circuits. We show that, starting from a function f : {0,1}l --> {0,1} computable in alternating time O(l) with O(1) alternations that ...
On the average-case complexity of MCSP and its variants
CCC '17: Proceedings of the 32nd Computational Complexity ConferenceWe prove various results on the complexity of MCSP (Minimum Circuit Size Problem) and the related MKTP (Minimum Kolmogorov Time-Bounded Complexity Problem):
• We observe that under standard cryptographic assumptions, MCSP has a pseudorandom self-...
Hardness amplification proofs require majority
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingHardness amplification is the fundamental task of converting a δ-hard function f : (0, 1)n -> (0, 1) into a (1/2-ε)-hard function Amp(f), where f is γ-hard if small circuits fail to compute f on at least a γ fraction of the inputs. Typically, ε,δ are ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 15 August 2011
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 16 Nov 2024