DocumentCode
1991632
Title
HyperSAT a new generator for 3-SAT instances
Author
Segura-Salazar, Juan ; Torres-Jiménez, José
Author_Institution
ITESM, Cuernavaca, Mexico
fYear
2001
fDate
2001
Firstpage
323
Lastpage
327
Abstract
Propositional satisfiability is the problem of determining, given a formula of propositional calculus in CNF (Conjunctive Normal Form), if there is an assignment of truth values for the variables in such a way that the whole formula is true. The SAT problem is one of the most important combinatorial optimization problems, in particular the 3-SAT problem is the,first NP-Complete problem. In order to test sat solving algorithms is necessary to generate hard sat instances, in this paper we address the construction and testing of HyperSAT a sat instance generator based on the concept of hypergraphs
Keywords
combinatorial mathematics; computability; computational complexity; graph theory; optimisation; 3-SAT problem; CNF; HyperSAT; NP-Complete problem; SAT problem; combinatorial optimization; computational complexity; hypergraphs; propositional calculus; propositional satisfiability; truth values; Calculus; NP-complete problem; Testing;
fLanguage
English
Publisher
ieee
Conference_Titel
Computational Intelligence and Multimedia Applications, 2001. ICCIMA 2001. Proceedings. Fourth International Conference on
Conference_Location
Yokusika City
Print_ISBN
0-7695-1312-3
Type
conf
DOI
10.1109/ICCIMA.2001.970487
Filename
970487
Link To Document