折纸折叠模式设计被证明是NP-Hard问题（转帖）

                            折纸折叠模式设计被证明是NP-Hard问题                                               

                                        matrix  发表于 2010年8月12日 16时28分 星期四        
                来自非确定性图灵机部门       
                                        
                                        折纸据说是起源自中国，但公认是在日本发扬光大。折纸是折叠纸张的艺术，它折出各种指定的形状和花样。过去几十年，很多人已经认识到，将正方形纸张折成任意3D形状的问题与计算几何学问题有很多类似之处。他们开发出计算机算法，能根据你指定的任何外形自动产生折叠模式。但是根据一项新的研究，设计复杂形状的折纸折叠模式对现在的计算机而言是“不可能完成的任务”，研究人员证明折纸折叠模式设计是NP-Hard问题——也就是说在有限时间是计算机不可能找到正确折叠方法。美国物理学家、著名折纸艺术家、折纸计算领域的权威Robert J.Lang和同事利用了一个技巧，通过让折纸折叠问题与另一个已知的NP-Hard问题——给定空间的Circle packing问题——等价起来，证明折纸也是NP-Hard问题。