×

zbMATH — the first resource for mathematics

A comparative runtime analysis of heuristic algorithms for satisfiability problems. (English) Zbl 1192.68655
Summary: The satisfiability problem is a basic core NP-complete problem. In recent years, a lot of heuristic algorithms have been developed to solve this problem, and many experiments have evaluated and compared the performance of different heuristic algorithms. However, rigorous theoretical analysis and comparison are rare. This paper analyzes and compares the expected runtime of three basic heuristic algorithms: RandomWalk, \((1+1)\) EA, and hybrid algorithm. The runtime analysis of these heuristic algorithms on two 2-SAT instances shows that the expected runtime of these heuristic algorithms can be exponential time or polynomial time. Furthermore, these heuristic algorithms have their own advantages and disadvantages in solving different SAT instances. It also demonstrates that the expected runtime upper bound of RandomWalk on arbitrary \(k\)-SAT \((k\geqslant 3)\) is \(O((k - 1)^n)\), and presents a \(k\)-SAT instance that has \(\Theta ((k - 1)^n)\) expected runtime bound.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q25 Analysis of algorithms and problem complexity
Software:
UnitWalk
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aarts, E.H.L.; Korst, J.H.M., Simulated annealing and Boltzmann machines, (1989), Wiley
[2] Alekhnovich, M.; Ben-Sasson, E., Linear upper bounds for random walk on small density random 3-CNF, SIAM journal on computing, 36, 5, 1248-1263, (2006) · Zbl 1124.68041
[3] Beame, P.; Kautz, H.; Sabharwal, A., Towards understanding and harnessing the potential of clause learning, Journal of artificial intelligence research, 22, 319-335, (2004) · Zbl 1080.68651
[4] Braunstein, A.; Mezard, M.; Zecchina, R., Survey propagation: an algorithm for satisfiability, Random structures & algorithms, 27, 2, 201-226, (2005) · Zbl 1087.68126
[5] Cook, S., The complexity of theorem-proving procedures, (), 151
[6] Davis, M.; Putnam, H., A computer procedure for quantification theory, Journal of the ACM, 7, 3, 202-215, (1960) · Zbl 0212.34203
[7] K.A. DeJong, W.M. Spears, Using genetic algorithm to solve NP-complete problems, in: Proceedings of the 3rd International Conference on Genetic Algorithms, Virginia, USA, 1989, pp. 124-132
[8] S. Droste, T. Jansen, I. Wegener, A natural and simple function which is hard for all evolutionary algorithms, in: Proceedings of Third Asia-Pacific Conference on Simulated Evolution and Learning, Nagaya, Japan, 2000, pp. 2704-2709
[9] Droste, S.; Jansen, T.; Wegener, I., On the analysis of the \((1 + 1)\)-evolutionary algorithm, Theoretical computer science, 276, 1-2, 51-81, (2002) · Zbl 1002.68037
[10] Garey, M.R.; Johnson, D.S., Computers and intractability—A guide to the theory of NP-completeness, (1979), Freeman New York · Zbl 0411.68039
[11] Garnier, J.; Kallel, L.; Schoenauer, M., Rigorous hitting times for binary mutations, Evolutionary computation, 7, 2, 167-203, (1999)
[12] Gottlieb, J.; Marchiori, E.; Rossi, C., Evolutionary algorithms for the satisfiability problem, Evolutionary computation, 10, 1, 35-50, (2002)
[13] Gu, J., Efficient local search for large-scale satisfiability problems, ACM SIGART bulletin, 3, 1, 8-12, (1992)
[14] He, J.; Yao, X., Towards an analytic framework for analyzing the computation time of evolutionary algorithms, Artificial intelligence, 145, 1-2, 59-97, (2003) · Zbl 1082.68802
[15] Hirsch, E.A.; Kojevnikov, A., Unitwalk: A new SAT solver that uses local search guided by unit clause elimination, Annals of mathematics and artificial intelligence, 43, 91-111, (2005) · Zbl 1100.68621
[16] Hoeffding, W., Probability inequalities for sums of bounded random variables, Journal of the American statistical association, 58, 301, 13-30, (1963) · Zbl 0127.10602
[17] Iosifescu, M., Finite Markov processes and their applications, (1980), John Wiley & Sons Chichester
[18] K. Iwama, S. Tamaki, Improved bounds for 3-SAT, in: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004, pp. 321-322
[19] Kirkpatrick, S.; Gelatt, C.D.; Vecchi, M.P., Optimization by simulated annealing, Science, 220, 671-680, (1983) · Zbl 1225.90162
[20] Lardeux, F.; Saubion, F.; Hao, J.K., GASAT: A genetic local search algorithm for the satisfiability problem, Evolutionary computation, 14, 2, 223-253, (2006)
[21] Levin, L.A., Universal search problems, Problemy peredachi informatsii, Problems of information transmission, 9, 3, 265-266, (1975), (in Russian), translation:
[22] Mezard, M.; Parisi, G.; Zecchina, R., Analytic and algorithmic solution of random satisfiability problems, Science, 297, 812-815, (2002)
[23] Motwani, R.; Raghavan, P., Randomized algorithms, (1995), Cambridge Univ. Press Cambridge, UK · Zbl 0849.68039
[24] Nix, A.E.; Vose, M.D., Modeling genetic algorithms with Markov chain, Annals of mathematics and artificial intelligence, 5, 1, 79-88, (1992) · Zbl 1034.68534
[25] C.H. Papadimitiou, On selecting a satisfying truth assignment, in: Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science, 1991, pp. 163-169
[26] Papadimitiou, C.H., Computational complexity, (1994), Addison Wesley
[27] Paturi, P.; Pudlak, P.; Saks, M.E.; Zane, F., An improved exponential-time algorithm for k-SAT, Journal of the ACM, 52, 3, 337-364, (2005) · Zbl 1297.68217
[28] D. Rolf, Improved bound for the PPSZ/Schöning-algorithm for 3-SAT, Electronic Colloquium on Computational Complexity (ECCC), Report No. 159, 2005
[29] U. Schöning, A probabilistic algorithm for k-SAT and constraint satisfaction problems, in: Proceedings of the 40th Annual Symposium on Foundation of Computer Science, 1999, pp. 410-414
[30] U. Schöning, Principles of stochastic local search, in: Proceedings of Sixth Conference on Unconventional Computation, Kingston, Canada, 2007, in: Lecture Notes in Computer Science, vol. 4618, 2007, pp. 178-187
[31] B. Selman, H. Levesque, D. Mitchell, A new method for solving hard satisfiability problems, in: Proceedings of Tenth National Conference on Artificial Intelligence (AAAI-92), San Jose, 1992, pp. 440-446
[32] B. Selman, H.A. Kautz, B. Cohen, Noise strategies for improving local search, in: Proceedings of Twelfth National Conference on Artificial Intelligence (AAAI-94), vol. 1, 1994, pp. 337-343
[33] W. Wei, B. Selman, Accelerating random walks, in: Proceedings of 8th Intl. Conference on the Principles and Practice of Constraint Programming (CP-2002), in: Lecture Notes in Computer Science, vol. 2470, 2002, pp. 216-232
[34] Zhang, H.; Stickel, M., Implementing the Davis Putnam method, Journal of automated reasoning, 24, 12, 277-296, (2000) · Zbl 0967.68148
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.