Satisfiability, branch-width and Tseitin tautologies
From MaRDI portal
(Redirected from Publication:430830)
Recommendations
Cites work
- scientific article; zbMATH DE number 4008289 (Why is no real title available?)
- scientific article; zbMATH DE number 65749 (Why is no real title available?)
- scientific article; zbMATH DE number 1256750 (Why is no real title available?)
- scientific article; zbMATH DE number 566078 (Why is no real title available?)
- scientific article; zbMATH DE number 2174386 (Why is no real title available?)
- A Separator Theorem for Planar Graphs
- An exponential separation between the parity principle and the pigeonhole principle
- Applications of a Planar Separator Theorem
- Graph minors. X: Obstructions to tree-decomposition
- Graph minors. XIII: The disjoint paths problem
- Intersection Theorems for Systems of Sets
- Mutilated chessboard problem is exponentially hard for resolution
- On Interpolation and Automatization for Frege Systems
- On the automatizability of resolution and related propositional proof systems
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- Pseudorandom Generators in Propositional Proof Complexity
- Resolution Is Not Automatizable Unless W[P] Is Tractable
- Short proofs are narrow—resolution made simple
- Solving satisfiability using decomposition and the most constrained subproblem
- The monotone circuit complexity of Boolean functions
- Width-parametrized SAT: time-space tradeoffs
Cited in
(30)- A SAT approach to branchwidth
- Tangle bases: Revisited
- Satisfiability of \(\operatorname{ECTL}^\ast\) with constraints
- On Tseitin formulas, read-once branching programs and treewidth
- Characterizing Tseitin-Formulas with Short Regular Resolution Refutations
- scientific article; zbMATH DE number 1113999 (Why is no real title available?)
- Computing branchwidth via efficient triangulations and blocks
- Theory and Applications of Satisfiability Testing
- Reflections on Proof Complexity and Counting Principles
- Special issue in memory of Misha Alekhnovich. Foreword
- On the hierarchical community structure of practical Boolean formulas
- Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
- Bounded-depth Frege complexity of Tseitin formulas for all graphs
- Expansion-based QBF solving versus Q-resolution
- Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs
- Size-treewidth tradeoffs for circuits computing the element distinctness function
- Variants and satisfiability in the infinitary unification wonderland
- Complexity and Algorithms for Well-Structured k-SAT Instances
- Characterizing Tseitin-formulas with short regular resolution refutations
- Logics in Artificial Intelligence
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Complexity and approximability of parameterized MAX-CSPs
- Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution
- On treewidth, separators and Yao's garbling
- An upper bound for resolution size: characterization of tractable SAT instances
- On the satisfiability of quantum circuits of small treewidth
- On the satisfiability of quantum circuits of small treewidth
- Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
- Backdoors to q-Horn
- Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
This page was built for publication: Satisfiability, branch-width and Tseitin tautologies
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q430830)
