Tighter hard instances for PPSZ

DOI10.4230/LIPICS.ICALP.2017.85zbMATH Open1441.68238arXiv1611.01291MaRDI QIDQ5111416FDOQ5111416

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

Publication date: 27 May 2020

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

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

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)

Cited In (7)

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

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)