SAT 2004 START ConferenceManager    


Visualizing the Internal Structure of SAT Instances (Preliminary Report)

Carsten Sinz

Presented at The Seventh International Conference on Theory and Applications of Satisfiability Testing (SAT 2004), Vancouver, BC, Canada, 10-13 May 2004


Abstract

Modern algorithms for the SAT problem reveal an almost tractable behavior on "real-world" instances. This is frequently assigned to the fact that these instances possess an internal "structure" that hard problem instances do not exhibit. However, little is known about this internal structure. We therfore propose the visualization of the instance's variable interaction graph as a first step of an empirical research program to analyze the internal problem structure. We present first results of such an analysis performed on instances of bounded model checking benchmark problems.


  
START Conference Manager (V2.47.2)
Maintainer: rrgerber@softconf.com