Name
Abstract | ||
|---|---|---|
To date, several types of structure for finite Constraint Satisfaction Problems have been investigated with the goal of either improving the performance of problem solvers or allowing efficient problem solvers to be identified. Our aim is to extend the work in this area by performing a structural analysis in terms of variable connectivity for 3-SAT problems. Initially structure is defined in terms of the compactness of variable connectivity for a problem. Using an easily calculable statistic developed to measure this compactness, a test was then created for identifying 3-SAT problems as either compact, loose or unstructured (or uniform). A problem generator was constructed for generating 3-SAT problems with varying degrees of structure. Using problems from this problem generator and existing problems from SATLIB, we investigated the effects of this type of structure on satisfiability and solvability of 3-SAT problems. For the same problem length, it is demonstrated that satisfiability and solvability are different for structured and uniform problems generated by the problem generator. |
Year | Venue | Keywords |
|---|---|---|
2002 | Australian Joint Conference on Artificial Intelligence | calculable statistic,3-sat problem,3-sat problems,variable connectivity,problem generator,structural analysis,variable relationships,problem length,uniform problem,problem solvers,finite constraint satisfaction problems,efficient problem solvers,constraint satisfaction problem,satisfiability,structure analysis |
Field | DocType | Volume |
Computer science,Satisfiability,Artificial intelligence,Finite geometry,Covering problems,Constraint satisfaction,Mathematical optimization,Boolean satisfiability problem,Algorithm,Constraint satisfaction problem,Compact space,Connectivity,Machine learning | Conference | 2557 |
ISSN | ISBN | Citations |
0302-9743 | 3-540-00197-2 | 1 |
PageRank | References | Authors |
0.38 | 16 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Olena Kravchuk | 1 | 1 | 0.38 |
| Wayne J. Pullan | 2 | 232 | 12.73 |
| John Thornton | 3 | 1 | 0.38 |
| abdul sattar | 4 | 1389 | 185.70 |