On the Hardness of SAT with Community Structure

DOI10.1007/978-3-319-40970-2_10zbMath1475.68353arXiv1602.08620OpenAlexW2290534980MaRDI QIDQ2818008

Sanjit A. Seshia, Nathan Mull, Daniel J. Fremont

Publication date: 5 September 2016

Published in: Theory and Applications of Satisfiability Testing – SAT 2016 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.08620

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

The impact of heterogeneity and geometry on the proof complexity of random satisfiability ⋮ Popularity-similarity random SAT formulas ⋮ Unnamed Item ⋮ On the Hardness of SAT with Community Structure ⋮ On the hierarchical community structure of practical Boolean formulas

Uses Software

• MiniSat

Cites Work

• Unnamed Item
• Generating SAT instances with community structure
• Backdoor sets of quantified Boolean formulas
• On the Hardness of SAT with Community Structure
• The Community Structure of SAT Formulas
• Impact of Community Structure on SAT Solver Performance
• Community Structure Inspired Algorithms for SAT and #SAT
• Many hard examples for resolution
• Blocked Clause Elimination
• Community structure in social and biological networks
• A Machine-Oriented Logic Based on the Resolution Principle
• A machine program for theorem-proving
• Theory and Applications of Satisfiability Testing

This page was built for publication: On the Hardness of SAT with Community Structure