A satisfiability algorithm and average-case hardness for formulas over the full binary basis
From MaRDI portal
(Redirected from Publication:354655)
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
Cites work
- scientific article; zbMATH DE number 3162894 (Why is no real title available?)
- scientific article; zbMATH DE number 1222558 (Why is no real title available?)
- scientific article; zbMATH DE number 1452705 (Why is no real title available?)
- scientific article; zbMATH DE number 5493266 (Why is no real title available?)
- 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
- A full derandomization of Schöning's \(k\)-\textsc{SAT} algorithm
- A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
- A satisfiability algorithm for \(\mathrm{AC}^0\)
- Affine extractors over prime fields
- Algorithms and Computation
- An algorithm for the satisfiability problem of formulas in conjunctive normal form
- An improved exponential-time algorithm for k -SAT
- Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms
- Hardness vs randomness
- Improving exhaustive search implies superpolynomial lower bounds
- On the construction of affine extractors
- On the hardness against constant-depth linear-size circuits
- Parity, circuits, and the polynomial-time hierarchy
- STACS 2004
- Solving satisfiability in less than \(2^ n\) steps
- The Shrinkage Exponent of de Morgan Formulas is 2
- The complexity of satisfiability of small depth circuits
- The effect of random restrictions on formula size
- \(\Sigma_ 1^ 1\)-formulae on finite structures
Cited in
(21)- Resolution over linear equations modulo two
- Mining circuit lower bound proofs for meta-algorithms
- Improved exact algorithms for mildly sparse instances of MAX SAT
- Improving \(3N\) circuit complexity lower bounds
- Fourier concentration from shrinkage
- Solving sparse instances of Max SAT via width reduction and greedy restriction
- On the complexity of unique circuit SAT
- Complete on average Boolean satisfiability
- A moderately exponential time algorithm for \(k\)-IBDD satisfiability
- Correlation bounds and \#SAT algorithms for small linear-size circuits
- Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
- Local restrictions from the Furst-Saxe-Sipser paper
- Gate elimination: circuit size lower bounds and \#SAT upper bounds
- Tighter connections between Formula-SAT and shaving logs
- An improved deterministic \#SAT algorithm for small De Morgan formulas
- Nonuniform ACC circuit lower bounds
- scientific article; zbMATH DE number 1543307 (Why is no real title available?)
- Tight upper bound on splitting by linear combinations for pigeonhole principle
- Exponential complexity of satisfiability testing for linear-size Boolean formulas
- Satisfiability algorithm for syntactic read-\(k\)-times branching programs
- Satisfiability algorithms and lower bounds for Boolean formulas over finite bases
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)
