《表1 现有平均复杂性问题的对比》

  提示：宽带有限、当前游客访问压缩模式

本系列图表出处文件名：随高清版一同展现

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

1. 获取 高清版本忘记账户？点击这里登录

1. 下载图表忘记账户？点击这里登录

一方面，有许多工作研究求解随机SAT的算法上，以找到易于求解的SAT问题上[16-18]。另一方面，有很多关于平均复杂性问题的构造。评价一个平均复杂性问题的好坏可以用三个参数衡量:首先，是问题的自然性；其次，是问题所服从分布的简单性；第三，是归约的初始问题的最坏复杂性。将现有结果从这三个角度进行了总结和对比，见表1。SIS、LWE问题和基于图论虽然是不同的组合问题，但通过适当的转换都可以转换成SAT问题（推论1）。因此，也将它们列入表中进行对比，如表1所示。