共查询到20条相似文献，搜索用时 15 毫秒
1.
说明 已经证明 ＧＣＨ和Ｐ≠ＮＰ ,及其他一些重要结果。整个证明包括三个部分 :一 , ＣＨ和Ｐ≠ＮＰ的间接证明 ;二 , ＧＣＨ的直接证明 ;三 , ＧＣＨ的形式证明。限于篇幅 ,本文只是第一部分 ( ＣＨ和Ｐ≠ＮＰ的间接证明 )的证明摘要 ,第一部分的所有证明细节及第二、第三部分的证明将在后续文章中给出。1 证明思路( 1 )根据Ｇ ｄｅｌ第一不完全性定理 ,对任一个数学的形式公理系统ＦＡ来说 ,如果ＦＡ满足 :①ＦＡ是真正形式的 ;②ＦＡ足够丰富 ,可以展开一个适量的数论 ;③ＦＡ是协调的 ,那么ＦＡ中至少包含一个命题Ｆ ,使得Ｆ和 Ｆ… 相似文献
2.
3.
4.
黄雄 《北京大学学报(自然科学版)》1995,31(5):556-562
研究了NP最优化问题的可近似性。按照不同的可近似性将问题分类,证明了这些类是不同的
（在P≠NP的假设下）,并定义了问题之间保持近似比的归约,为每一类找到了在此归约下完
全的问题。 相似文献
5.
许道云 《贵州大学学报(自然科学版)》2003,20(3):225-235
合取范式(CNF)公式H到F的同态是一个从H的文字集合到F的文字集合的映射、并保持补运算和子句映到子句。同态映射保持一个公式的不可满足性。一个公式是极小不可满足的是指公式不可满足而且从中删去任一个子句后得到的公式可满足。MU(1)是子句数与变元数的差等于1的极小不可满足公式类。S．Szeider证明了：每个不可满足公式F是MU(1)中某个公式日的同态像。从而，基于MU(1)的同态证明系统与树消解证明系统是p-等价的。MU(1)中的公式可以用基础矩阵表示，本文用基础矩阵的方法证了同态证明系统ПMU（1）的完备性。 相似文献
6.
讨论两台机器上的有序流水作业时间表问题，证明两台机器上的有序流水作业时间表问题是ＮＰ－困难的。 相似文献
7.
给出了密钥覆盖问题的模型建立过程,并从顶点覆盖问题的判定形式出发,证明了密钥覆盖问题的判定形式是NP完全问题,为组通信安全的研究,尤其是多播安全的研究奠定了更为坚实的基础. 相似文献
8.
杨汉兴 《武汉科技大学学报(自然科学版)》1998,(4)
Ｌａｗｌｅｒ和Ｌｅｎｓｔｒａ已证明［１］：赋有延误惩罚的单机排序问题是强ＮＰ－完全问题，没有多项式时间算法。笔者曾证明［２］：如果附加条件ｐｉ≥ｐＪｐｉ／ｗｉ＞ｐｊ／ｗｊ对于所有的ｉ≠ｊ（ｉ，ｊ＝１，２，…，ｎ）成立，则该问题有伪多项式时间算法。现在研究如何用动态规划方法求解这类排序问题。 相似文献
9.
10.
本研究以百合鳞片为外植体，用叶盘法将兔防御素ＮＰ－１基因导入百合中，经培养获得再生植株，通过抗生素筛选和ＰＣＲ分析，证帝为转基因植株，同时，地农杆菌转化过程中的一些影响因素进行了探讨。 相似文献
11.
12.
研究了3种有限自动机,即二维二方向的确定型、非确定型以及Las Vegas有限自动机.证明存在语言能被二维二方向的Las Vegas有限自动机识别,但不能被相应的确定型有限自动机识别;存在语言能被二维二方向的非确定型有限自动机识别,但不能被相应的Las Vegas有限自动机识别.研究结果表明,二维二方向的Las Vegas有限自动机所识别的语言真包含确定型有限自动机所识别的语言;二维二方向的非确定型有限自动机所识别的语言真包含Las Vegas有限自动机所识别的语言. 相似文献
13.
本文证明了风向图上两问题是ＮＰ－完全的和强ＮＰ－完全的，并进一步指出：即使所给风向图是平面的，它们仍是ＮＰ－完全的及强ＮＰ－完全的，这两个问题是：一是叫２ＷＰＰ，它是由风和中投递员穿过每条边至多两次而得到的问题；另一问题是风向图上最大权圈装箱问题。 相似文献
14.
杨振华 《南京邮电大学学报(自然科学版)》2001,21(4):64-66
建立了一种染色问题的数学模型 ,利用模 2意义下的矩阵表示 ,将原问题归结为线性方程组的求解 ,从而给出了一个多项式算法 相似文献
15.
16.
空间方向关系推理问题的NP完全性证明是基于两个重要的变换基础之上的，其中一个变换是把空间方向关系推理问题变换为一个限定满足问题，基于这种变换，空间方向关系推理问题中的变量和值域相应地变换为限定满足问题中的空间目标和方向关系限制；另一个变换是从不全等3可满足问题到方向关系限定满足问题，基于这种变换，3可满足问题实例中的变量可以变换为两个方向关系限制。为此，一个满足所有目标方向关系限制的空间结构可以建立，从而可以证明空间方向关系推理问题的NP完全性性质。 相似文献
17.
18.
19.
徐银如 《华东师范大学学报(自然科学版)》1990,(2):1-7
本文就Fedorov的所谓线性最优准则,给出W-算法在非奇异和奇异最优设计中收敛到线性最优设计的统一的证明,从而解决了W-算法在很广的一类最优设计中的收敛性问题. 相似文献