最大节约原则下单体型推导问题的复杂性

基于最大节约原则,寻找可以解释基因型样本的最小单体型集合,提出一个新的单体型推导方法.通过将SAT问题和MAX-3-SAT问题归约到这种基于节约原则的单体型推导问题,证明了该问题是NP-hard以及MAX-SNP完全的,从而解决了该问题在计算上的复杂性.这一结果显示,除非P等于NP,否则,该问题不存在多项式时间算法;甚至存在一个常数e> 0,该问题不存在比1 e好的近似算法.     

有限制的通用模糊图灵机研究

给出了模糊图灵机的几种等价形式,包括具有分明转移函数的模糊图灵机(FNTMc)、模糊图灵机(FNTM)以及模糊多带图灵机.利用模糊图灵机,定义了模糊递归枚举语言与模糊递归语言,并给出它们的层次刻画,证明了不存在通用模糊图灵机;如果限制模糊集的隶属函数为单位区间[0,1]的固定有限子集D,对应的模糊图灵机称为限制型模糊图灵机,则存在通用的限制型模糊图灵机,而且这类图灵机可以以任意给定精度模拟其他模糊图灵机,从而通用模糊图灵机在逼近意义下是存在的.     

NP最优化问题的可近似性

研究了NP最优化问题的可近似性。按照不同的可近似性将问题分类,证明了这些类是不同的 （在P≠NP的假设下）,并定义了问题之间保持近似比的归约,为每一类找到了在此归约下完 全的问题。     

一种广义分子计算模型在集合覆盖中的应用

在分子计算原理和传统计算机模型基础上,提出了一种新的基于图灵机的广义分子计算模型,又称广义图灵模型,该模型的具体实现不依赖于特定生物技术. 模型继承分子计算大存储高并行的特点,通过时空复杂度转换,在求解NP完全问题上具有通用性. 模型由一台基本图灵机、一个只写带和一条工作带及读写网络这3部分组成,其中只写带和工作带之间存在一种特殊拓扑映射. 通过数据规模为4的集合覆盖问题,证明该算法能在多项式时间内求解集合覆盖问题,验证了算法和模型的有效性.     

可满足性问题的充分必要条件

可满足性问题是计算机和人工智能领域内的一个重要的问题,是第一个被证明是NPC的问题。本文主要把子句集进行分类,给出翻转定义、简单集定义,翻转同构定义,并且证明翻转同构不改变子句集的可满足性。论文证明了可满足子句集的三个充要条件。并且这些充要条件可以用于判断可满足问题的完全搜索和不完全搜索算法。     

可满足性问题的充分必要条件

可满足性问题是计算机和人工智能领域内的一个重要的问题,是第一个被证明是NPC的问题。本文主要把子句集进行分类,给出翻转定义、简单集定义,翻转同构定义,并且证明翻转同构不改变子句集的可满足性。论文证明了可满足子句集的三个充要条件。并且这些充要条件可以用于判断可满足问题的完全搜索和不完全搜索算法。     

广义分子计算模型在整数问题中的应用

分子计算是一种新型的并行计算模式. 作为信息载体和计算载体的DNA,生化反应时存在不可控性. 构建具有通用性的分子计算机存在许多困难和限制. 将分子计算黏贴模型与图灵机相结合,已提出一种不依赖于特定生物技术的广义分子计算模型(generalized turing model,GTM). 对GTM模型进行扩展,通过实验说明了该广义分子计算机能够在多项式时间内求解NP完全的整数规划问题,该模型具有编码简单、错误率低等特点.     

基于膜计算模型的数独游戏基本解法

为了更好地求解数独问题,提出了一种新的求解方法,利用一个具有抑制催化和膜溶解规则以及进化规则的优先级的膜系统来进行求解;结果表明,对于一个数独问题,只要其所有部分解都至少包含一个具有唯一解的单元格,方法都是有效的;如果数独问题可以利用此策略求解,则膜系统在计算的最后一步将问题的解编码并返回物质YES,否则,膜系统可以检测出数独问题不符合上述特征,返回物质NO,计算停止;方法求解策略与人类求解数独问题的思考过程非常类似,并且给出的是数独问题的统一解,即与数独问题的维度和提示数无关。     

交错扩散对于Turing不稳定现象的影响

对建立在生态学基础上的一类具有Hlling-Ⅲ型功能性响应函数的捕食常微分模型及其对应的偏微分模型进行研究,发现交错扩散可以把不稳定的只具有自扩散的偏微分方程组变成稳定的偏微分系统,也可以把稳定的变成不稳定的系统.     

四则运算图灵机的构造

著名的丘奇(A．Church)命题指出，任何算法都可以用一个图灵机来描述．对自然数的四则运算给出了相应的图灵机．     

一种求解SAT问题的人工蜂群算法

针对SAT问题,提出一种求解该问题的离散人工蜂群算法——ABCSAT算法,建立了相应的优化算法模型,解决了问题编码和转化、适应度函数、蜜蜂觅食策略、离散操作等关键问题.不同于处理连续优化问题,ABCSAT将适应度函数定义为当前不可满足子句数.根据问题的特点设计了多种觅食策略,并利用各子句和变量之间约束关系的启发式信息对各阶段的候选解进行离散操作.最后在标准SATLIB测试集上对提出的算法进行了测试并与相关算法进行了比较,结果验证了ABCSAT算法在中小规模SAT问题上的有效性,表明算法能更加有效地解决该问题.     

线性加工时间单机成组排序问题

讨论一类线性加工时间成组排序问题．在这一模型中，工件的加工时间是其开工时间的线性函数，全部工件分成若干组．工件的加工必须满足成组技术限制，同组工件间没有安装时间，各组间有与顺序无关的安装时间．目标函数为极小化最大完工时间．基于对问题的分析，给出了多项式算法。     

独立分量分析法改进商图像

商图像方法是一种处理人脸识别中光线变化问题的简便方法,但其存在理想类假设不准确以及三维点光源无法很好地近似任意光照情况两个问题。针对这些不足,本文利用最小二乘法解决不准确理想类的问题,并提出了一种基于独立分量分析的商图像改进方法,解决三维点光源模型无法很好地近似任意光照情况的问题。仿真实验结果表明:所提方法与原方法相比具有更好的图像合成效果和人脸识别性能。     

交换机中周期流优化调度问题的复杂性

研究了交换机中周期流量的优化调度问题,着重讨论了该问题的复杂性.依据呼损率定义了交换机周期流量调度的最优化问题,并对其子问题,嵌套周期流优化调度的复杂性进行了研究.证明了一种受限Max2Sat问题的NP完全性,并通过将该问题多项式归约到交换机周期流量调度的最优化问题,由此证明了仅有1和2周期的交换机周期流优化调度问题是强NPC问题.并利用该结果证明了任意嵌套周期的优化调度问题也是强NPC的.这表明对于任意嵌套周期流优化调度问题不存在伪多项式算法.     

带不可用时间段的不允许等待柔性流水排序问题

给出了极小化时间表长带不可用时间段限制的不允许等待柔性流水车间排序问题的模型,并对其算法复杂性进行分析.分析的结果表明,该问题在几乎所有情况下都不存在具有有限最坏比的多项式时间算法.     

关于相对化的P与NP问题的若干研究

研究相对化的Ｐ＝？ＮＰ问题，提出了矛盾天书、相对天书和绝对天书的概念，证明了这些天书的客观存在性，并具体地构造了一个矛盾天书和一个ＮＰ集类之外的相对天书．结论对利用现有关于相对化Ｐ＝？ＮＰ问题的成果来研究ＮＰ问题将产生有益的影响     

带运输时间的Flow-shop时间表问题

研究带运输时间的流水作业时间表问题，同一工件在一台机器上完工之后，在另一台机器上开始加工，且运输过程只能由机器R完成，证明在只有两台机器的情况下，该问题是强NP-困难的，并构造一个启发式算法，证明该算法的紧界为2。     

少儿图灵测试和常识处理

This talk presents our research work on children Turing test. It is implemented in a conversation system supported by a commonsense knowledge base. This system can talk to school children in a more or less natural way. The main difference between it and many other conversation programs is its knowledgebased character. In this talk, motivation of children Turing test and the analysis of its results will be described. We will analyze the achievements and failures of children Turing test, its main bottlenecks, its modified versions and its relation to commonsense knowledge processing. In addition, we will propose some conjectures on Turing test under certain hypotheses and give some concluding remarks.