|
|||||
|
|
| 一个具有平均复杂性的SAT问题 | |
| 作者单位： | ;1.中国科学技术大学中国科学院电磁空间信息重点实验室 |
| 摘 要： | 最坏复杂性到平均复杂性的归约已被研究很多年。很多NP困难问题是最坏复杂性的。distNP类是平均复杂性的NP类,且有完全问题。LIVEN N证明了所有自然的NP完全问题都有平均复杂性的形式,但是他给出的概率分布是不自然的。在格问题方面,AJTAI和REGEV O分别提出了平均复杂性的困难问题,即短整数解问题(Short Integer Solution,SIS)和带错误学习问题(Learning With Errors,LWE)。给出一个可以归约到判定对于一个NP完全问题是否存在多项式时间算法,对值为1的实例给出一个见证,并且对值为0的实例给出一个归结辩驳的具有平均复杂性的SAT问题。本文方法是将求解NP完全问题的多项式时间算法的存在性转化成SAT问题的一组实例。同时也给出了这个问题的一些变形问题。 |
An average-case complete version of SAT |
|
| Abstract: | |
| Keywords: | NP coNP 平均复杂性 LWE |