Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
An Improved Satisfiable SAT Generator Based on Random Subgraph Isomorphism
verfasst von : Cǎlin Anton
Erschienen in: Advances in Artificial Intelligence
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We introduce Satisfiable Random High Degree Subgraph Isomorphism Generator(SRHD-SGI), a variation of the Satisfiable Random Subgraph Isomorphism Generator (SR-SGI). We use the direct encoding to translate the SRHD-SGI instances into Satisfiable SAT instances. We present empirical evidence that the new model preserves the main characteristics of SAT encoded SR-SGI: easy-hard-easy pattern of evolution and exponential growth of empirical hardness. Our experiments indicate that SAT encoded SRHD-SGI instances are empirically harder than their SR-SGI counterparts. Therefore we conclude that SRHD-SGI is an improved generator of satisfiable SAT instances.