摘要
From the SAT physical model, a physical hypothesis named PHHY is proposed. By PHHY, it is proved that there is a universally efficient algorithm for solving SAT problem. Then, by square packing problem, the authors show that there are interesting industrial NP-complete problems which can be solved through SAT algorithms, but each way of solving like this will be much worse than that of a certain direct solving.
From the SAT physical model, a physical hypothesis named PHHY is proposed. By PHHY, it is proved that there is a universally efficient algorithm for solving SAT problem. Then, by square packing problem, the authors show that there are interesting industrial NP-complete problems which can be solved through SAT algorithms, but each way of solving like this will be much worse than that of a certain direct solving.
基金
Project supported by the Chinese High-Tech Program, the National Natural Science Foundation of China and the Chinese Science Fou
