On converting CNF to DNF
From MaRDI portal
Publication:2576880
DOI10.1016/j.tcs.2005.07.029zbMath1080.94018MaRDI QIDQ2576880
Jaikumar Radhakrishnan, Peter Bro Miltersen, Ingo Wegener
Publication date: 29 December 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2005.07.029
Related Items
Invariant inference with provable complexity from the monotone theory, Courcelle's theorem -- a game-theoretic approach, Practical algorithms for MSO model-checking on tree-decomposable graphs, Improving resolution width lower bounds for \(k\)-CNFs with applications to the strong exponential time hypothesis, On the structure and the number of prime implicants of 2-\(\mathsf{CNF}\)s, On the resolution and optimization of a system of fuzzy relational equations with sup-\(T\) composition, Cable tree wiring -- benchmarking solvers on a real-world scheduling problem with a variety of precedence constraints, Static analysis and stochastic search for reachability problem, Cryptanalysis of Boyen's attribute-based encryption scheme in TCC 2013, ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Solving satisfiability in less than \(2^ n\) steps
- The tail of the hypergeometric distribution
- A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
- Minimal polynomials for the conjunction of functions on disjoint variables can be very simple
- A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
- A very simple function that requires exponential size read-once branching programs.
- Performance Tuning an Algorithm for Compressing Relational Tables
- An improved exponential-time algorithm for k -SAT
- Branching Programs and Binary Decision Diagrams
- Mathematical Foundations of Computer Science 2003
- On Cores and Prime Implicants of Truth Functions
- Theory and Applications of Satisfiability Testing
- Natural proofs
