Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


Carlos Zamora Thesis.pdf (30.05 MB)

ETD Abstract Container

Abstract Header

HAMMING DISTANCE PLOT TECHNIQUES FOR SLS SAT SOLVERS: EXPLORING THE BEHAVIOR OF STATE-OF-THE-ART SLS SOLVERS ON RANDOM K-SAT PROBLEMS

Zamora, Carlos Enrique, Jr
http://rave.ohiolink.edu/etdc/view?acc_num=case1554825851959352

Abstract Details

2019, Master of Sciences, Case Western Reserve University, EECS - Computer and Information Sciences.
Stochastic local search (SLS) algorithms have been recognized for their efficiency in solving random k-SAT problems. At the SAT Competition in 2016, WalkSatlm, FrwCB, and DCCASat were three original SLS solvers that performed particularly well. In this thesis, I present three new visual representation techniques for SAT solvers based on Hamming distance measurements: unsat clause plots, HD(s)-USS plots, and HD(s)- HD(t) plots. Additionally, I introduce three modifications to FrwCB. These plot tech- niques were able to distinguish the better performing algorithms from the worse. This is more clearly seen on large problems below the conjectured satisfiability threshold. They also reveal more information about the search conducted by the solvers.
Harold Connamacher, Dr. (Advisor)
Harold Connamacher, Dr. (Committee Chair)
Soumya Ray, Dr. (Committee Member)
Vincenzo Liberatore, Dr. (Committee Member)
207 p.
Artificial Intelligence; Computer Science
SAT; satisfiability; hamming distance; configuration checking; plot; unsat stack size; random k-SAT

Recommended Citations

Citations

  • Zamora, Jr, C. E. (2019). HAMMING DISTANCE PLOT TECHNIQUES FOR SLS SAT SOLVERS: EXPLORING THE BEHAVIOR OF STATE-OF-THE-ART SLS SOLVERS ON RANDOM K-SAT PROBLEMS [Master's thesis, Case Western Reserve University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=case1554825851959352

    APA Style (7th edition)

  • Zamora, Jr, Carlos. HAMMING DISTANCE PLOT TECHNIQUES FOR SLS SAT SOLVERS: EXPLORING THE BEHAVIOR OF STATE-OF-THE-ART SLS SOLVERS ON RANDOM K-SAT PROBLEMS. 2019. Case Western Reserve University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=case1554825851959352.

    MLA Style (8th edition)

  • Zamora, Jr, Carlos. "HAMMING DISTANCE PLOT TECHNIQUES FOR SLS SAT SOLVERS: EXPLORING THE BEHAVIOR OF STATE-OF-THE-ART SLS SOLVERS ON RANDOM K-SAT PROBLEMS." Master's thesis, Case Western Reserve University, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=case1554825851959352

    Chicago Manual of Style (17th edition)

case1554825851959352
164
© 2019, all rights reserved.
This open access ETD is published by Case Western Reserve University School of Graduate Studies and OhioLINK.