• Articles • Previous Articles     Next Articles

A Hopeful CNF-SAT─Algorithm Its High Efficiency, Industrial Application and Limitation

Huang Wenqi; Li Wei;   

  1. Department of Computer Science; Huazhong University of Science & Technology Wuhan 430074; P.R. China; Department of Computer Science; Beijing University of Aeronautics and Astronautics Beijing 100085; P.R. China;
  • Online:1998-01-10 Published:1998-01-10

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.

Key words: knowledge representation and reasoning; techniques of algorithms; constraint satisfaction; Boolean satisfiability; penalty formulation; saddle point; search;



[1] Huang Wenqi, Li Wei, Lu Weifeng, Zhang Yuping. A physical model for the satisfiability problem. Lecture Notes in Computer Science 959 Springer. In Proc. First Annual International Conference, Cocoon'95, Xi'an, China, August 1995.

[2] Li Wei, Huang Wenqi. A mathematic-physical approach to the satisfiability problem. In Science in China, Series A, Nov. 1994 (in Chinese), Jan. 1995 (in English).

[3] Huang Wenqi. Solving CNF-SAT problem by ordinary differential equation method. In Proc. National Symposium, on Dyreamical System (in Chinese), Xinin, Black Horse River, July 1994. ……….
[1] Dong-Hui Yang, Zhen-Yu Li, Xiao-Hui Wang, Kavé Salamatian, Gao-Gang Xie. Exploiting the Community Structure of Fraudulent Keywords for Fraud Detection in Web Search [J]. Journal of Computer Science and Technology, 2021, 36(5): 1167-1183.
[2] Yi-Ting Wang, Jie Shen, Zhi-Xu Li, Qiang Yang, An Liu, Peng-Peng Zhao, Jia-Jie Xu, Lei Zhao, Xun-Jie Yang. Enriching Context Information for Entity Linking with Web Data [J]. Journal of Computer Science and Technology, 2020, 35(4): 724-738.
[3] Hong-Fei Xu, Yu Gu, Jian-Zhong Qi, Jia-Yuan He, Ge Yu. Diversifying Top-k Routes with Spatial Constraints [J]. Journal of Computer Science and Technology, 2019, 34(4): 818-838.
[4] Xin-Chen Liu, Wu Liu, Hua-Dong Ma, Shuang-Qun Li. PVSS: A Progressive Vehicle Search System for Video Surveillance Networks [J]. Journal of Computer Science and Technology, 2019, 34(3): 634-644.
[5] Fateh Boucenna, Omar Nouali, Samir Kechid, M. Tahar Kechadi. Secure Inverted Index Based Search over Encrypted Cloud Data with User Access Rights Management [J]. Journal of Computer Science and Technology, 2019, 34(1): 133-154.
[6] Rim Mahouachi. Search-Based Cost-Effective Software Remodularization [J]. Journal of Computer Science and Technology, 2018, 33(6): 1320-1336.
[7] Geng Lin, Jian Guan. A Binary Particle Swarm Optimization for the Minimum Weight Dominating Set Problem [J]. , 2018, 33(2): 305-322.
[8] Ming-Liang Xu, Ning-Bo Gu, Wei-Wei Xu, Ming-Yuan Li, Jun-Xiao Xue, Bing Zhou. Mechanical Assembly Packing Problem Using Joint Constraints [J]. , 2017, 32(6): 1162-1171.
[9] Ai-Hua Yin, Tao-Qing Zhou, Jun-Wen Ding, Qing-Jie Zhao, Zhi-Peng Lv. Greedy Randomized Adaptive Search Procedure with Path-Relinking for the Vertex p-Center Problem [J]. , 2017, 32(6): 1319-1333.
[10] Peng Jiang, Yi Mu, Fuchun Guo, Qiao-Yan Wen. Private Keyword-Search for Database Systems Against Insider Attacks [J]. , 2017, 32(3): 599-617.
[11] Ze-Qi Lin, Bing Xie, Yan-Zhen Zou, Jun-Feng Zhao, Xuan-Dong Li, Jun Wei, Hai-Long Sun, Gang Yin. Intelligent Development Environment and Software Knowledge Graph [J]. , 2017, 32(2): 242-249.
[12] Hai-Da Zhang, Zhi-Hao Xing, Lu Chen, Yun-Jun Gao, Senior Member, CCF, Member, ACM, IEEE. Efficient Metric All-k-Nearest-Neighbor Search on Datasets Without Any Index [J]. , 2016, 31(6): 1194-1211.
[13] Xusheng Xiao, Jian-Guang Lou, Shan Lu, David C. Shepherd, Xin Peng, Qian-Xiang Wang. Roundtable: Research Opportunities and Challenges for Large-Scale Software Systems [J]. , 2016, 31(5): 851-860.
[14] Xiao-Fen Wang, Yi Mu, Rongmao Chen, Xiao-Song Zhang. Secure Channel Free ID-Based Searchable Encryption for Peer-to-Peer Group [J]. , 2016, 31(5): 1012-1027.
[15] Jing Wu, Paul L. Rosin, Xianfang Sun, Ralph R. Martin. Improving Shape from Shading with Interactive Tabu Search [J]. , 2016, 31(3): 450-462.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved