-
题名MAX和MARG中公式改名的复杂性(英文)
- 1
-
-
作者
许道云
-
机构
贵州大学计算机科学系
-
出处
《南京大学学报（数学半年刊）》
CAS
2006年第2期181-199,共19页
-
基金
Supported by the National Natural Science Foundation of China (No. 60463001,No. 10410638, No. 60310213).
-
文摘
研究了判定问题“对于命题CNF公式F和H,是否存在一个变元(或文字)改名(?),使得(?)(F)=H?”的复杂性．对于极小不可满足公式的子类MAX和MARG,我们证明了:其变元改名和文字改名的复杂性等价于图同构问题GI．
-
关键词
复杂性
变元改名
文字改名
极小不可满足公式
图同构
-
Keywords
complexity, variable renaming, literal renaming, minimal unsatisfiable formula, graph isomorphism.
-
分类号
TP18
[自动化与计算机技术—控制理论与控制工程]
-
-
题名一个极小不可满足公式子类的等价结构(英文)
- 2
-
-
作者
许道云
-
机构
贵州大学计算机科学系
-
出处
《贵州大学学报（自然科学版）》
2001年第2期79-89,102,共12页
-
基金
ProjectsupportedbythenaturalsciencefoundationofGuizhouUniversity
-
文摘
研究一个极小不可满足公式子类 (MAX( 1 ) )的等价结构 考虑了MAX( 1 )上的变元改名问题和文字改名问题 此两个问题均可在O(nlog2 (n) )
-
关键词
极小不可满足公式
变元改名
等价结构
文字改名
MAX(1)
O时间
-
Keywords
minimal unsatisfiable formula,renaming,equivalence structure.
-
分类号
O24
[理学—计算数学]
-
