3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General

DOI10.1109/FOCS.2011.22zbMATH Open1292.68092OpenAlexW2120698547MaRDI QIDQ5494972FDOQ5494972

Authors: Timon Hertli 

Publication date: 30 July 2014

Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2011.22

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Cited In (16)

• Towards NP-P via proof complexity and search
• What's next? Future directions in parameterized complexity
• Title not available (Why is that?)
• Local reduction
• Backdoors to satisfaction
• An improvement of the algorithm of Hertli for the unique 3SAT problem
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• A combinatorial analysis for the critical clause tree
• A new upper bound for \(( n , 3)\)-MAX-SAT
• A satisfiability algorithm for \(\mathrm{AC}^0\)
• On the exact complexity of evaluating quantified \(k\)-\textsc{cnf}
• PPSZ for general \(k\)-SAT and CSP -- making Hertli's analysis simpler and 3-SAT faster
• On the optimality of exact and approximation algorithms for scheduling problems
• Solving SCS for bounded length strings in fewer than \(2^n\) steps
• Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT
• Local reductions

This page was built for publication: 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General

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