Concrete Physics Method for Solving NP hard Problem  

作　　者：Huang Wen\|qi College of Computer Science, Huazhong University of Science and Technology, Wuhan 430074,China Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100080, China 

出　　处：《Wuhan University Journal of Natural Sciences》2001年第Z1期140-146,共7页武汉大学学报（自然科学英文版）

基　　金：86 3National High-Tech Program of China(86 3-30 6 -0 5 -0 3-1) ;National Natural Science Foundation of China(193310 5 0 ) ;Chi

摘　　要：With a NP hard problem given, we may find a equivalent physical world. The rule of the changing of the physical states is simply the algorithm for solving the original NP hard problem .It is the most natural algorithm for solving NP hard problems. In this paper we deal with a famous example , the well known NP hard problem——Circles Packing. It shows that our algorithm is dramatically very efficient. We are inspired that, the concrete physics algorithm will always be very efficient for NP hard problem.With a NP hard problem given, we may find a equivalent physical world. The rule of the changing of the physical states is simply the algorithm for solving the original NP hard problem .It is the most natural algorithm for solving NP hard problems. In this paper we deal with a famous example , the well known NP hard problem——Circles Packing. It shows that our algorithm is dramatically very efficient. We are inspired that, the concrete physics algorithm will always be very efficient for NP hard problem.

关 键 词：concrete physics algorithm NP hard problem circles packing the rule of the changing of the physical states 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]