The complexity of satisfiability problems
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- Existentially restricted quantified constraint satisfaction
- A minimization version of a directed subgraph homeomorphism problem
- Universal algebra and hardness results for constraint satisfaction problems
- The complexity of satisfiability problems: Refining Schaefer's theorem
- Stable matching problems with exchange restrictions
- Relatively quantified constraint satisfaction
- Partially ordered connectives and monadic monotone strict NP
- The SAT-UNSAT transition for random constraint satisfaction problems
- Using clausal graphs to determine the computational complexity of \(k\)-bounded positive one-in-three SAT
- An efficient algorithm for Horn description
- On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls
- A combinatorial constraint satisfaction problem dichotomy classification conjecture
- NP-hard and linear variants of hypergraph partitioning
- On recovering syntenic blocks from comparative maps
- Bases for Boolean co-clones
- A surprising permanence of old motivations (a not-so-rigid story)
- An algorithm for exact satisfiability analysed with the number of clauses as parameter
- Combinatorial analysis (nonnegative matrices, algorithmic problems)
- Complete problems for space bounded subclasses of NP
- Implications of forbidden structures for extremal algorithmic problems
- Scheduling tasks on two processors with deadlines and additional resources
- The complexity of minimizing wire lengths in VLSI layouts
- Polynomially solvable satisfiability problems
- Shortest enclosing walks and cycles in embedded graphs
- Observations concerning a public-key cryptosystem based on iterated morphisms
- A hierarchy of propositional Horn formuls
- Reasoning with minimal models: efficient algorithms and applications
- Backtracking with multi-level dynamic search rearrangement
- An NP-complete matching problem
- NP-completeness of some generalizations of the maximum matching problem
- On minimum dominating sets with minimum intersection
- Correlation polytopes: Their geometry and complexity
- The complexity of model checking for circumscriptive formulae
- A hierarchy of tractable satisfiability problems
- Complexity of path-forming games
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- On some bandwidth restricted versions of the satisfiability problem of propositional CNF formulas
- Constraints, consistency and closure
- On the algebraic structure of combinatorial problems
- The complexity of some problems related to GRAPH 3-COLORABILITY
- On the computational complexity of reconstructing lattice sets from their X-rays
- A two-phase algorithm for solving a class of hard satisfiability problems
- Deciding whether a planar graph has a cubic subgraph is NP-complete
- The \(k\)-SATISFIABILITY problem remains NP-complete for dense families
- The complexity of propositional closed world reasoning and circumscription
- Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
- Causal approximations
- On the complexity of some basic problems in computational convexity. I. Containment problems
- Polynomial-time inference of all valid implications for Horn and related formulae
- The complexity of minimum partial truth assignments and implication in negation-free formulae
- Recognition complexity for Schaefer classes
- Satisfiability problems on intervals and unit intervals
- Generalized satisfiability problems: Minimal elements and phase transitions.
- The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
- Some variants of SAT and their properties
- Optimal satisfiability for propositional calculi and constraint satisfaction problems.
- Learnability of quantified formulas.
- Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights
- On stable cutsets in graphs
- Conjunctive-query containment and constraint satisfaction
- The NP-completeness of (1,r)-subcolorability of cubic graphs
- Pushing vertices in digraphs without long induced cycles
- Nominal unification with atom-variables
- Towards a characterization of constant-factor approximable finite-valued CSPs
- Circuit satisfiability and constraint satisfaction around Skolem arithmetic
- On the complexity of trial and error for constraint satisfaction problems
- Decidability and complexity for quiescent consistency and its variations
- On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
- Finding non-orientable surfaces in 3-manifolds
- On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions
- Out-degree reducing partitions of digraphs
- Crane scheduling in railway yards: an analysis of computational complexity
- On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
- On the complexity of graph coloring with additional local conditions
- Partition of a binary matrix into \(k\) (\(k \geq 3\)) exclusive row and column submatrices is difficult
- On bijunctive predicates over a finite set
- Network pollution games
- A hypocoloring model for batch scheduling
- New algorithms for exact satisfiability
- Realizability and verification of MSC graphs
- Balanced vertex-orderings of graphs
- A new tractable class of constraint satisfaction problems
- On the complexity of deciding typability in the relational algebra
- The complexity of Boolean constraint satisfaction local search problems
- Exact 3-satisfiability is decidable in time \(O(2^{0.16254 n})\)
- Degree constrained 2-partitions of semicomplete digraphs
- Pushing the frontier of minimality
- Sorting, linear time and the satisfiability problem
- Bandwidth contrained NP-complete problems
- Investigations on autark assignments
- Faster exact solutions for some NP-hard problems.
- On the Hamming distance of constraint satisfaction problems.
- Complexity of nilpotent unification and matching problems.
- Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
- Tractable reasoning via approximation
- A perspective on certain polynomial-time solvable classes of satisfiability
- Fast approximate probabilistically checkable proofs
- Dichotomies for classes of homomorphism problems involving unary functions
- The complexity of minimal satisfiability problems
- On the complexity of minmax regret linear programming
This page was built for publication: The complexity of satisfiability problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5402560)
