On converting CNF to DNF
From MaRDI portal
Publication:2576880
DOI10.1016/j.tcs.2005.07.029zbMath1080.94018OpenAlexW2064149002MaRDI 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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (10)
Cryptanalysis of Boyen's attribute-based encryption scheme in TCC 2013 ⋮ Improving resolution width lower bounds for \(k\)-CNFs with applications to the strong exponential time hypothesis ⋮ Courcelle's theorem -- a game-theoretic approach ⋮ Invariant inference with provable complexity from the monotone theory ⋮ On the structure and the number of prime implicants of 2-\(\mathsf{CNF}\)s ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Static analysis and stochastic search for reachability problem ⋮ ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS ⋮ 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
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
This page was built for publication: On converting CNF to DNF
