欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
研究了判定问题“对于命题CNF公式F和H，是否存在一个变元（或文字）改名φ，使得φ（F）=H？”的复杂性．对于极小不可满足公式的子类MAX和MARG，我们证明了：其变元改名和文字改名的复杂性等价于图同构问题GI．
英文摘要：
We investigate the complexity of deciding whether for propositional CNF formulas F and H there exists a variable renaming or a literal renaming φ such that φ（F） = H. For the subclasses MAX and MARG of minimal unsatisfiable formulas, we show that the variable and literal renaming problems are equivalent to the graph isomorphism problem GI.
同期刊论文项目
同项目期刊论文
期刊信息
位置：