ML Anthology

On Minimum Representations of Matched Formulas (Extended Abstract)

Ondrej Cepek, Stefan Gurský, Petr Kucera
IJCAI 2017 pp. 4980-4984
doi:10.24963/IJCAI.2017/706 /ijcai/2017/cepek2017ijcai-minimum/

Abstract

A Boolean formula in conjunctive normal form (CNF) is called matched if the system of sets of variables which appear in individual clauses has a system of distinct representatives. We present here two results for matched CNFs: The first result is a shorter and simpler proof of the fact that Boolean minimization remains complete for the second level of polynomial hierarchy even if the input is restricted to matched CNFs. The second result is structural --- we show that if a Boolean function f admits a representation by a matched CNF then every clause minimum CNF representation of f is matched.

PDF IJCAI Semantic Scholar

Cite

Text

Cepek et al. "On Minimum Representations of Matched Formulas (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2017. doi:10.24963/IJCAI.2017/706

Markdown

[Cepek et al. "On Minimum Representations of Matched Formulas (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2017.](https://mlanthology.org/ijcai/2017/cepek2017ijcai-minimum/) doi:10.24963/IJCAI.2017/706

BibTeX

@inproceedings{cepek2017ijcai-minimum,
  title     = {{On Minimum Representations of Matched Formulas (Extended Abstract)}},
  author    = {Cepek, Ondrej and Gurský, Stefan and Kucera, Petr},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2017},
  pages     = {4980-4984},
  doi       = {10.24963/IJCAI.2017/706},
  url       = {https://mlanthology.org/ijcai/2017/cepek2017ijcai-minimum/}
}