On converting CNF to DNF

DOI10.1016/j.tcs.2005.07.029zbMath1080.94018MaRDI QIDQ2576880

Ingo Wegener, Jaikumar Radhakrishnan, Peter Bro Miltersen

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

zbMATH Keywords

disjunctive normal form; circuit size; conjunctive normal form; switching lemma

Mathematics Subject Classification ID

Related Items

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, 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