Generating Random SAT Instances: Multiple Solutions could be Predefined and Deeply Hidden

DOI10.1613/JAIR.1.13909MaRDI QIDQ5881807zbMATH OpenOpenAlexFDO

Authors Dongdong Zhao, Lei Liao, Wenjian Luo, Hao Jiang, Xiao-Yi Hu

Publication date 13 March 2023

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1613/jair.1.13909

zbMATH Keywords

constraint programmingsatisfiabilityprobabilistic reasoning

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Reasoning under uncertainty in the context of artificial intelligence (68T37)

Recommendations

• Generating hard satisfiable formulas by hiding solutions deceptively
• A wealth of SAT distributions with planted assignments
• Generating Difficult CNF Instances in Unexplored Constrainedness Regions
• Unique solution instance generation for the 3-satisfiability (3SAT) problem
• scientific article; zbMATH DE number 956856

Cites work

• scientific article; zbMATH DE number 780774 (Why is no real title available?)
• scientific article; zbMATH DE number 1448978 (Why is no real title available?)
• scientific article; zbMATH DE number 2243408 (Why is no real title available?)
• (If) size matters: size-hiding private set intersection
• A model of random industrial SAT
• Bounded size-hiding private set intersection
• Generating SAT instances with community structure
• Generating hard satisfiability problems
• Generating hard satisfiable formulas by hiding solutions deceptively
• Hiding the input-size in secure two-party computation
• Lower bounds for random 3-SAT via differential equations
• Many hard examples in exact phase transitions
• Popularity-similarity random SAT formulas
• Random constraint satisfaction: easy generation of hard (satisfiable) instances

Cited in

(3)

• Generating Diverse Solutions in SAT
• Generating Difficult CNF Instances in Unexplored Constrainedness Regions
• Zero-One Designs Produce Small Hard SAT Instances

This page was built for publication: Generating Random SAT Instances: Multiple Solutions could be Predefined and Deeply Hidden

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