Solving satisfiability in less than \(2^ n\) steps
From MaRDI portal
Publication:1082830
DOI10.1016/0166-218X(85)90050-2zbMath0603.68092MaRDI QIDQ1082830
Ewald Speckenmeyer, Burkhard Monien
Publication date: 1985
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Related Items
An improved upper bound for SAT ⋮ A lower bound for tree resolution ⋮ Counting minimal unsatisfiable subsets ⋮ A simplified NP-complete MAXSAT problem ⋮ Efficient 3-SAT algorithms in the tile assembly model ⋮ European Summer Meeting of the Association for Symbolic Logic ⋮ Local search algorithms for SAT: Worst-case analysis ⋮ Computing Maximal Autarkies with Few and Simple Oracle Queries ⋮ Polynomial-average-time satisfiability problems ⋮ A new algorithm for the propositional satisfiability problem ⋮ Exploiting partial knowledge of satisfying assignments ⋮ Density condensation of Boolean formulas ⋮ A satisfiability algorithm and average-case hardness for formulas over the full binary basis ⋮ Unnamed Item ⋮ A fast parallel SAT-solver -- efficient workload balancing ⋮ Derandomizing the HSSW algorithm for 3-SAT ⋮ Minimal sets on propositional formulae. Problems and reductions ⋮ A general method for deciding about logically constrained issues ⋮ A new bound for 3-satisfiable MaxSat and its algorithmic application ⋮ A Decision-Making Procedure for Resolution-Based SAT-Solvers ⋮ A CNF Class Generalizing Exact Linear Formulas ⋮ Towards NP-P via proof complexity and search ⋮ An approximation algorithm for 3-Colourability ⋮ A randomized algorithm for 3-SAT ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ An artificial neural network satisfiability tester ⋮ Approximating minimal unsatisfiable subformulae by means of adaptive core search ⋮ Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. ⋮ Worst-case study of local search for MAX-\(k\)-SAT. ⋮ Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets ⋮ Homomorphisms of conjunctive normal forms. ⋮ A combinatorial analysis for the critical clause tree ⋮ An exact algorithm for the Boolean connectivity problem for \(k\)-CNF ⋮ On the parameterized complexity of \((k,s)\)-SAT ⋮ New methods for 3-SAT decision and worst-case analysis ⋮ On a generalization of extended resolution ⋮ Complexity analysis of propositional resolution with autarky pruning ⋮ On \(k\)-positive satisfiability problem ⋮ A CNF Formula Hierarchy over the Hypercube ⋮ Truth Assignments as Conditional Autarkies ⋮ Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT ⋮ Separating signs in the propositional satisfiability problem ⋮ Number of models and satisfiability of sets of clauses ⋮ Multilevel descriptions of classes decreasing the number of steps in solving pattern recognition problems described by propositional formulas ⋮ Autark assignments of Horn CNFs ⋮ The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs ⋮ An efficient algorithm for the 3-satisfiability problem ⋮ Fixed-parameter tractability of satisfying beyond the number of variables ⋮ A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications ⋮ Pseudo-Boolean optimization ⋮ Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable ⋮ On the complexity of \(k\)-SAT ⋮ UnitWalk: A new SAT solver that uses local search guided by unit clause elimination ⋮ MAX SAT approximation beyond the limits of polynomial-time approximation ⋮ Improving Efficiency of 3-SAT-Solving Tile Systems ⋮ Guided Search and a Faster Deterministic Algorithm for 3-SAT ⋮ CASCADING RANDOM WALKS ⋮ О весах булевых функций, представимых в виде $2$-КНФ или $3$-КНФ ⋮ Strong extension-free proof systems ⋮ A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application ⋮ Molecular computing, bounded nondeterminism, and efficient recursion ⋮ A new lower bound on approximability of the ground state problem for tridimensional Ising spin glasses ⋮ Efficient Reasoning for Inconsistent Horn Formulae ⋮ Solving and sampling with many solutions: Satisfiability and other hard problems ⋮ Investigations on autark assignments ⋮ Present and Future of Practical SAT Solving ⋮ CNF satisfiability in a subspace and related problems ⋮ On converting CNF to DNF ⋮ Faster exact solutions for some NP-hard problems. ⋮ A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search. ⋮ A short note on some tractable cases of the satisfiability problem. ⋮ Unnamed Item ⋮ Which problems have strongly exponential complexity?
Cites Work
