NP完全问题多项式时间算法研究

本文从代数及组合两个方面论证了NP完全问题存在多项式时间算法 .以往利用线性规划 (LP)技术来分析NP完全问题中的TSP问题 ,因其存在子环游问题 ,从而使问题得不到有效解决 .文中发展一分层网络 ,在求解TSP问题时 ,存在另一类(不完全 )子环游问题 .但两模型允许解集的交集避免了两类子环游基本可行解 ,从而使TSP问题可利用LP技术多项式时间内得以解决 ,同时给出了求哈密尔顿回路的多项式标记证明方法 ,开创了NPC问题研究的新局面 .

Study on the Polynomial-time Algorithms of NP Complete Problems

In this paper, the polynimial time algorithms of the NP complete problems are gained in the algebraical and combinatorial two aspects respectively. Since there were subtours, the linear programming (LP) technics was inefficient in the past, which was used to analysed the travelling salesman problem (TSP). A layer network is developed in the paper, there are another type (uncomplete) subtours. However, the intersect set of the feasible solution sets of the two models don't contain the two subtours basic feasible solution, hence the TSP is solved in polynomial time using LP technics. Meanunile, a polynomial-time lebeling method is gived to search a Hamilton circuit in a graph. Therefore, a new area to analyse the NPC problem is developed.