【摘 要】
：
本文从代数及组合两个方面论证了NP完全问题存在多项式时间算法 .以往利用线性规划 (LP)技术来分析NP完全问题中的TSP问题 ,因其存在子环游问题 ,从而使问题得不到有效解决 .
论文部分内容阅读
本文从代数及组合两个方面论证了NP完全问题存在多项式时间算法 .以往利用线性规划 (LP)技术来分析NP完全问题中的TSP问题 ,因其存在子环游问题 ,从而使问题得不到有效解决 .文中发展一分层网络 ,在求解TSP问题时 ,存在另一类(不完全 )子环游问题 .但两模型允许解集的交集避免了两类子环游基本可行解 ,从而使TSP问题可利用LP技术多项式时间内得以解决 ,同时给出了求哈密尔顿回路的多项式标记证明方法 ,开创了NPC问题研究的新局面 .
其他文献
设（Ｘｔ）是有转移函数的马尔可夫过程，其中Ｘｔ取值于状态空间（Ｅｔ，ξ，ｔ≥０。设ｆｔ是（Ｅｔ，ξ）到状态空间（Ｅｔ，ξ是的可测变换。本文给出了使（ｆｔ（Ｘｔ）仍是有转移函数的马尔可夫过程的充分条件，对于有函数的马尔可夫过程族
本文引入且用次梯度集该划Ｂａｎａｃｈ空间上凸函数的上、下指数，得到共轭凸函数上、下指数间的完整共轭关系、正齐次凸函数是Ｍｉｎｋｏｖｓｋｉ规函数的幂等结果，已有的一维相关结果是本文的特例。
本文讨论离散时间代数Ｒｉｃｃａｔｉ方程ＡＴＸＡ－Ｘ－（ＡＴＸＢ＋Ｌ）（Ｒ＋ＢＴＸＢ）＾－１（ＬＴ＋ＢＴＸＡ）＋Ｑ＝０的唯一对称正定解的上界和下界。
设Ｎ是中心为Ｚ的素近环，Ｉ是Ｎ的右理想，Ｄ是Ｎ上的非平凡导子，本文证明了１）若Ｄ（Ｉ）∈Ｚ，则（Ｎ１＋）是交换的；又若Ｎ２－挠自由，则Ｎ是无零因子交换环，（２）若０≠Ｄ＾ｎ（Ｉ）∈Ｚ，Ｄ＾ｎ－１（Ｉ）∈Ｉ，且Ｎ是（ｎ＋１）１挠自由的，则Ｎ是无零因子交换环。
本文给出了当V0 ≥ 0时 ,c′σ2 在混合模型M =( y ,Xβ ,Uξ,σ20 V0 )下的最小范数二次无偏估计的表达式及其证明 ;得到了当 y服从正态分布时 ,c′σ2 的最小范数二次无偏
本文考虑一维非等熵流气体动力学方程组Ｃａｕｃｈｙ问题。在临界情形ａ＝１，我们得到了经典解生命跨度的估计。
文「１」中证明了弱阻尼非线性Ｓｃｈｒｏｄｉｎｇｅｒ方程在无界区域Ｒ＾Ｎ上存在一个最大的紧吸引子，本文在此基础上得到了Ｒ＾３上指数吸引子的存在性。
建立了一类中立型时滞抛物微分方程系统的振动的若干充分条件。
本文论述了与四色宣等价的几个新命题，从而给出了平面三角剖分及圈上的４染色集的一些新性质，钭平面图的４可染色问题转化为圈上的４染色来研究，这将更便于用计算机来寻找关于四色定理
研究非线性分布时滞系统最优控制，提出一种基于线性分布时滞模型和二次型性能指标问题的迭代算法，将分布时滞系统化为满足马尔可夫性质的增广状态系统，在模型和实际存在差异的情