A satisfiability algorithm and average-case hardness for formulas over the full binary basis

DOI10.1007/s00037-013-0067-7zbMath1286.68208OpenAlexW2104306727MaRDI QIDQ354655

Kazuhisa Seto, Suguru Tamaki

Publication date: 19 July 2013

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2433/189761

zbMATH Keywords

satisfiabilityexact algorithmaverage-case hardnessformulaparity gate

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (18)

A Moderately Exponential Time Algorithm for k-IBDD Satisfiability ⋮ An improved deterministic \#SAT algorithm for small De Morgan formulas ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits ⋮ Improved exact algorithms for mildly sparse instances of MAX SAT ⋮ Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases ⋮ Unnamed Item ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ Solving sparse instances of Max SAT via width reduction and greedy restriction ⋮ On the complexity of unique circuit SAT ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ Local restrictions from the Furst-Saxe-Sipser paper ⋮ Fourier concentration from shrinkage ⋮ Tight Upper Bound on Splitting by Linear Combinations for Pigeonhole Principle ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ Resolution over linear equations modulo two ⋮ Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs ⋮ Mining circuit lower bound proofs for meta-algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Derandomizing the HSSW algorithm for 3-SAT
• Affine extractors over prime fields
• On the construction of affine extractors
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Solving satisfiability in less than \(2^ n\) steps
• A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
• Hardness vs randomness
• Improving exhaustive search implies superpolynomial lower bounds
• Parity, circuits, and the polynomial-time hierarchy
• Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms
• An improved exponential-time algorithm for k -SAT
• On the Hardness against Constant-Depth Linear-Size Circuits
• The Complexity of Satisfiability of Small Depth Circuits
• The Shrinkage Exponent of de Morgan Formulas is 2
• An algorithm for the satisfiability problem of formulas in conjunctive normal form
• The effect of random restrictions on formula size
• Algorithms and Computation
• STACS 2004
• A full derandomization of schöning's k-SAT algorithm
• 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General

This page was built for publication: A satisfiability algorithm and average-case hardness for formulas over the full binary basis