Unique solution instance generation for the 3-satisfiability (3SAT) problem

MaRDI QIDQ2749863zbMATH OpenFDO

Authors Mitsuo Motoki, Ryuhei Uehara

Publication date 21 October 2001

zbMATH Keywords

3-satisfiability problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Uniquely satisfiable \(k\)-SAT instances with almost minimal occurrences of each variable
• An improvement of the algorithm of Hertli for the unique 3SAT problem
• scientific article; zbMATH DE number 1113991
• Generating hard satisfiable formulas by hiding solutions deceptively
• Probabilistic performance of a heurisic for the satisfiability problem

Cited in

(3)

• Generating Random SAT Instances: Multiple Solutions could be Predefined and Deeply Hidden
• Generating instances for MAX2SAT with optimal solutions
• An improvement of the algorithm of Hertli for the unique 3SAT problem

Describes a project that uses

Uses Software

• Walksat

This page was built for publication: Unique solution instance generation for the 3-satisfiability (3SAT) problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2749863)