一个具有平均复杂性的SAT问题

摘要

最坏复杂性到平均复杂性的归约已被研究很多年。很多NP困难问题是最坏复杂性的。distNP类是平均复杂性的NP类,且有完全问题。LIVEN N证明了所有自然的NP完全问题都有平均复杂性的形式,但是他给出的概率分布是不自然的。在格问题方面,AJTAI和REGEV O分别提出了平均复杂性的困难问题,即短整数解问题(Short Integer Solution,SIS)和带错误学习问题(Learning With Errors,LWE)。给出一个可以归约到判定对于一个NP完全问题是否存在多项式时间算法,对值为1的实例给出一个见证,并且对值为0的实例给出一个归结辩驳的具有平均复杂性的SAT问题。本文方法是将求解NP完全问题的多项式时间算法的存在性转化成SAT问题的一组实例。同时也给出了这个问题的一些变形问题。