Tighter hard instances for PPSZ

DOI10.4230/LIPICS.ICALP.2017.85MaRDI QIDQ5111416zbMATHFDO

Authors Pavel Pudlák, D. Scheder, Navid Talebanfard

Publication date 27 May 2020

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

zbMATH Keywords

resolutionstrong exponential time hypothesis\(k\)-SATPPSZ

Mathematics Subject Classification ID

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

Recommendations

• Exponential lower bounds for the PPSZ \(k\)-SAT algorithm
• PPSZ for general \(k\)-SAT -- making Hertli's analysis simpler and 3-SAT faster
• 3-SAT faster and simpler -- unique-SAT bounds for PPSZ hold in general
• Breaking the PPSZ barrier for unique 3-SAT
• PPSZ for \(k\geq 5\): more is better

Cited in

(7)

• PPSZ for \(k\geq 5\): more is better
• PPSZ for general \(k\)-SAT -- making Hertli's analysis simpler and 3-SAT faster
• Exponential lower bounds for the PPSZ \(k\)-SAT algorithm
• PPSZ for general \(k\)-SAT and CSP -- making Hertli's analysis simpler and 3-SAT faster
• On super strong ETH
• 3-SAT faster and simpler -- unique-SAT bounds for PPSZ hold in general
• Super strong ETH is true for PPSZ with small resolution width

This page was built for publication: Tighter hard instances for PPSZ

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