On the structure and the number of prime implicants of 2-CNFs

DOI10.1016/J.DAM.2015.06.036MaRDI QIDQ906424zbMATH OpenOpenAlexFDO

Authors Navid Talebanfard

Publication date 21 January 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.2662

zbMATH Keywords

Boolean functioncombinatorial problemscomputational complexityconjunctive normal formprime implicant

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Abstract: Let $m(n,k)$ be the maximum number of prime implicants that any $k$-CNF on n variables can have. We show that $3^{n/3}lem(n,2)le(1+o(1))3^{n/3}$.

Cites work

• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• An improved exponential-time algorithm for k -SAT
• On k-Term DNF with the Largest Number of Prime Implicants
• On cliques in graphs
• On converting CNF to DNF
• On the number of prime implicants

Cited in

(1)

• Connected Boolean functions with a locally extremal number of prime implicants

This page was built for publication: On the structure and the number of prime implicants of 2-\(\mathsf{CNF}\)s

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q906424)