A satisfiability algorithm and average-case hardness for formulas over the full binary basis
From MaRDI portal
Publication:354655
DOI10.1007/S00037-013-0067-7zbMATH Open1286.68208OpenAlexW2104306727MaRDI QIDQ354655FDOQ354655
Authors: 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
Recommendations
- Satisfiability algorithms and lower bounds for Boolean formulas over finite bases
- An algorithm for the satisfiability problem of formulas in conjunctive normal form
- Exponential complexity of satisfiability testing for linear-size Boolean formulas
- CNF-Satisfiability Test by Counting and Polynomial Average Time
- Solving satisfiability in less than \(2^ n\) steps
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Hardness vs randomness
- The complexity of satisfiability of small depth circuits
- Parity, circuits, and the polynomial-time hierarchy
- Solving satisfiability in less than \(2^ n\) steps
- An algorithm for the satisfiability problem of formulas in conjunctive normal form
- A satisfiability algorithm for \(\mathrm{AC}^0\)
- Improving exhaustive search implies superpolynomial lower bounds
- Title not available (Why is that?)
- The Shrinkage Exponent of de Morgan Formulas is 2
- Title not available (Why is that?)
- The effect of random restrictions on formula size
- A full derandomization of Schöning's \(k\)-\textsc{SAT} algorithm
- Affine extractors over prime fields
- On the construction of affine extractors
- A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
- 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
- Derandomizing the HSSW algorithm for 3-SAT
- Title not available (Why is that?)
- Algorithms and Computation
- STACS 2004
- 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
Cited In (21)
- Fourier concentration from shrinkage
- Mining circuit lower bound proofs for meta-algorithms
- Correlation bounds and \#SAT algorithms for small linear-size circuits
- Exponential complexity of satisfiability testing for linear-size Boolean formulas
- Tighter connections between Formula-SAT and shaving logs
- Satisfiability algorithm for syntactic read-\(k\)-times branching programs
- Complete on average Boolean satisfiability
- Improving \(3N\) circuit complexity lower bounds
- Resolution over linear equations modulo two
- Nonuniform ACC circuit lower bounds
- An improved deterministic \#SAT algorithm for small De Morgan formulas
- Solving sparse instances of Max SAT via width reduction and greedy restriction
- Title not available (Why is that?)
- A moderately exponential time algorithm for \(k\)-IBDD satisfiability
- Gate elimination: circuit size lower bounds and \#SAT upper bounds
- Satisfiability algorithms and lower bounds for Boolean formulas over finite bases
- Local restrictions from the Furst-Saxe-Sipser paper
- On the complexity of unique circuit SAT
- Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
- Improved exact algorithms for mildly sparse instances of MAX SAT
- Tight upper bound on splitting by linear combinations for pigeonhole principle
This page was built for publication: A satisfiability algorithm and average-case hardness for formulas over the full binary basis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q354655)
