首页    期刊浏览 2024年09月15日 星期日
登录注册

文章基本信息

  • 标题:Syntactic Isomorphism of CNF Boolean Formulas is Graph Isomorphism Complete
  • 本地全文:下载
  • 作者:Giorgio Ausiello ; Francesco Cristiano ; Luigi Laura
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2012
  • 卷号:2012
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We investigate the complexity of the syntactic isomorphism problem of CNF Boolean Formulas (CSFI): given two CNF Boolean formulas (a1an) and (b1bn) decide whether there exists a permutation of clauses, a permutation of literals and a bijection between their variables such that (a1an) and (b1bn) become syntactically identical. We first show that the CSFI problem is polynomial time reducible to the graph isomorphism problem (GI) and then we show that GI is polynomial time reducible to a special case of the CSFI problem (MCSFI) that is CSFI-complete and also GI-complete, thus concluding that the syntactic isomorphism problem for CNF Boolean formulas is GI-complete. Finally we observe that the same results hold when considering DNF Boolean formulas (DSFI).

  • 关键词:Boolean formulas; boolean isomorphism; complexity theory; Graph Isomorphism; semantic isomorphism; syntactic isomorphism
国家哲学社会科学文献中心版权所有