资源分类
》 资源 》论文》On Minimum Representations of Matched Formulas (Extended Abstract)

On Minimum Representations of Matched Formulas (Extended Abstract)

2019-10-29 | |  47 |   42 |   0
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

上一篇：On Coalitional Manipulation for Multiwinner Elections: Shortlisting

下一篇：On the Expressivity of Inconsistency Measures (Extended Abstract)?

用户评价
全部评价

热门资源

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Rating-Boosted La...

    The performance of a recommendation system reli...