Complexity of DNF minimization and isomorphism testing for monotone formulas

Judy Goldsmith, Matthias Hagen, Martin Mundhenk

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

We investigate the complexity of finding prime implicants and minimum equivalent DNFs for Boolean formulas, and of testing equivalence and isomorphism of monotone formulas. For DNF related problems, the complexity of the monotone case differs strongly from the arbitrary case. We show that it is DP-complete to check whether a monomial is a prime implicant for an arbitrary formula, but the equivalent problem for monotone formulas is in L. We show PP-completeness of checking if the minimum size of a DNF for a monotone formula is at most k, and for k in unary, we show that the complexity of the problem drops to coNP. In Christopher Umans [Christopher Umans, The minimum equivalent DNF problem and shortest implicants, Journal of Computer and System Sciences 63 (4) (2001) 597-611] a similar problem for arbitrary formulas was shown to be ∑2p-complete. We show that calculating the minimum equivalent DNF for a monotone formula is possible in output-polynomial time if and only if P = NP. Finally, we disprove a conjecture from Steffen Reith [Steffen Reith, On the complexity of some equivalence problems for propositional calculi, in: Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS), vol. 2747, Lecture Notes in Computer Science, Springer, 2003, pp. 632-641] by showing that checking whether two formulas are isomorphic has the same complexity for arbitrary formulas as for monotone formulas.

Original languageEnglish
Pages (from-to)760-775
Number of pages16
JournalInformation and Computation
Volume206
Issue number6
DOIs
StatePublished - Jun 2008

Bibliographical note

Funding Information:
* Corresponding author. Fax: +49 3641 946002. E-mail addresses: goldsmit@cs.uky.edu (J. Goldsmith), hagen@cs.uni-jena.de (M. Hagen), mundhenk@cs.uni-jena.de (M. Mundhenk). 1 Partially supported by NSF Grant ITR-0325063. 2 Partially supported by a Landesgraduiertenstipendium Thüringen.

Keywords

  • Computational complexity
  • Formula isomorphism
  • Monotone formulas
  • Prime implicants

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Complexity of DNF minimization and isomorphism testing for monotone formulas'. Together they form a unique fingerprint.

Cite this