期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

一个从k-CNF到t-CNF归约的有效算法 被引量：7

AN EFFECTIVE ALGORITHM FOR REDUCING K-CNF TO T-CNF
在线阅读 下载PDF
导出
摘要 根据极小不可满足公式的特征,对于固定的3 ≤t＜k.我们给出了一个将k-CNF公式归约到t-CNF公式的有效算法.对于给定的k-CNF公式F,t-CNF公式的转换可以在公式F的长度的线性时间内完成.
作者 王健 许道云
机构地区 贵州大学计算机科学系
出处 《南京大学学报（数学半年刊）》 CAS 2005年第1期53-65,共13页 Journal of Nanjing University(Mathematical Biquarterly)
基金 国家自然科学基金，the Foundation of Government of Guizhou Province，贵州省科学发展研究专项基金
关键词 极小不可满足公式 归约 算法
分类号 O141.1 [理学—基础数学]
  • 相关文献

参考文献9

  • 1Aharoni R. Minimal Non-Two-Colorable Hypergraphs and Minimal Unsatisfiable Formulas. J. Com.Theory, Ser. 1996, A(43): 196-204.
  • 2Davydov G, Davydova I and Kleine Buining H. An Efficient Algorithm for the Minimal Unsatisfiability Problem for a Subclass of CNF. Anna. Math. Artificial Intelligence, 1998, 23: 229-245.
  • 3Fleischner H, Kullmann O and Szeider S. Polynomial-Time Recognition of Minimal Unsatisfiable Formulas with Fixed Clause-Variable Difference. Theoretical Computer Science, 2002. 289(1): 503-516.
  • 4Garey M R and Johnson D S. Computers and Intractability A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979.
  • 5Kleine Brining H. On Subclasses of Minimal Unsatisfiable Formulas. Discrete Applied Mathematics,2000, 107: 83-98.
  • 6Kleine Buning H and Lettman T. Propositional Logic: Deduction and Algorithms. Cambridge University Press, 1999.
  • 7Kleine Buning H and Xu D Y. The Complexity of Homomorphisms and Renamings for Minimal Unsatisfiable Formulas. Anna. Math. Artificial Intelligence, 2005, 43(1-4): 113-127.
  • 8Impagilazzo R and Paturi R. Complexity of k-SAT. Proceedings Fourteenth Annual IEEE Conference on Computational Complexity, 1999, 4(6): 237-240.
  • 9Xu D Y. On the Complexity of Renamings and Homomorphisms for Minimal Unsatisfiable Formulas. Dissertation, Nanjing University in China, 2002.

同被引文献13

引证文献7

二级引证文献20

南京大学学报（数学半年刊）
2005年 第1期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部