|
|||||
|
|
| 求解析取范式永真性问题的一个近似快速算法 | |
| 引用本文： | 宋恩民.求解析取范式永真性问题的一个近似快速算法[J].科学通报,1992,37(8):676-676. |
| 作者姓名： | 宋恩民 |
| 作者单位： | 华中理工大学计算机系，华中理工大学计算机系 武汉 430074，武汉 430074 |
| 摘 要： | NP完全问题是一类在计算复杂性理论中被证明为较难求解的问题,这类问题中包含有很多在理论和实际中很有意义的问题。NP完全问题中的一个问题的对偶问题若存在快速(多项式意义下)的求解算法,则所有NP完全问题都有快速的求解算法。但目前人们还没有找到一个求解NP完全问题的真正快速算法,并且有迹象表明求解NP完全问题的真正快速算法是不存在的。本文针对一个典型的NP完全问题的对偶问题——析取范式永真性 |
| 关 键 词： | 折取范式 永真性 NP完全问题 算法 |
| 本文献已被 CNKI 维普 等数据库收录！ | |
| 点击此处可从《科学通报》浏览原始摘要信息 | |
| 点击此处可从《科学通报》下载免费的PDF全文 | |