可用概率验证的证明和编码

导出

摘要 NP是一个复杂性类，对于该类问题很容易验证其解的正确性．相反地，寻找NP问题的解通常是很困难的．SAT（可满足问题）就是一个经典的例子：给定一个布尔公式，构造一个满足公式的赋值是非常困难的，而对给定的一个赋值却很容易代入公式来验证其正确性．这样的一个赋值就称为布尔公式的可满足性的一个“NP一证明”．

作者 Irit Dinur 刘克(译) 吴凌云(校)

机构地区以色列Weizmann科学研究所应用数学与计算机科学部不详

出处《数学译林》 2011年第1期2-2,共1页 MATHEMATICS

关键词验证证明编码概率 NP问题可满足问题可满足性公式

分类号 TP301.6 [自动化与计算机技术—计算机系统结构]

引文网络
相关文献

1王勋,宋建民,贺毅朝.基于遗传算法求解NPC的研究[J].河南科技学院学报（自然科学版）,2014,42(6):40-45. 被引量：1
2李思昆,张建民,沈胜宇.布尔不可满足子式的求解方法研究进展[J].计算机辅助设计与图形学学报,2008,20(10):1253-1260. 被引量：1
3邵明,李光辉,李晓维.求解可满足问题的调查传播算法以及步长的影响规律[J].计算机学报,2005,28(5):849-855. 被引量：8
4刘忆宁,曹建宇.基于概率验证的移动会议方案[J].计算机工程与应用,2010,46(26):109-110.
5陈庆,叶妙,张益新.多银行的公正的可分电子现金系统[J].计算机应用,2003,23(9):99-102. 被引量：2
6王勋,宋建民,贺毅朝.基于遗传算法求解NPC问题的研究[J].河北省科学院学报,2014,31(4):1-7.
7秦永彬,许道云.警示传播算法的原理分析及算法改进[J].计算机工程与应用,2010,46(19):1-6. 被引量：3
8张建民,沈胜宇,李思昆.基于悖论证明与局部搜索的不可满足子式求解算法[J].计算机学报,2014,37(11):2262-2267. 被引量：4
9朱大铭,马绍汉,张平平.合取范式3可满足问题的局部搜索近似算法[J].计算机学报,2010,33(7):1127-1139. 被引量：1
10林奋,周育人.求解可满足问题的改进的蚁群算法[J].计算机工程与应用,2009,45(3):42-44. 被引量：6

数学译林

2011年第1期

浏览历史

内容加载中请稍等...

可用概率验证的证明和编码

相关作者

相关机构

相关主题

浏览历史