In this paper we propose a new approach for developing a proof that P=NP. We propose to use a polynomial-time reduction of a NP-complete problem to Linear Programming. Earlier such attempts used polynomial-time transformation which is a special form of reduction that uses a subroutine for the easier Linear Programming Problem only once. We use multiple calls to the subroutine increasing considerably the effectiveness of the reduction. Further the NP-complete problem we choose is also unusual. We define a special kind of acyclic directed graph which we call a time graph. We define Hamiltonian time paths in such graphs and also the Hamiltonian Time Path problem (HTPATH) and prove that it is NP-complete. We then state a conjecture whose proof will immediately lead to a polynomial-time algorithm for this problem proving P=NP.
翻译:在本文中,我们提出一种新的方法来开发P=NP的证明。 我们建议对线性编程使用多度时间减少一个NP完整的问题。 早些时候,这种尝试使用了多度时间转换, 这是一种特殊的递减形式, 仅一次使用亚例来减少较简单的线性编程问题。 我们在子例中多次调用, 大大提高了减少的效果。 我们选择的NP完成问题也是不寻常的。 我们定义了一种特殊的周期性直线图, 我们称之为时间图。 我们在这些图表中定义了汉密尔顿时间路径以及汉密尔顿时间路径问题( HTPATH ), 并证明它是NP- 完成的。 然后我们提出一个预测, 其证据将立即导致对该问题的多度时间算法, 证明 P=NP 。