下面的NP hard或P方程的证明

Question

所以我想解决旅行推销员的正式声明：输入完整的加权有向图G和目标整数k如果存在通过G的路径>>，则输出true

1) visits every vertex exactly once
2) costs <= k
使用：输入：有向网格图G，一组目标点S和一个整数k输出：如果有一条通过G的路径最多以左拐k到达S的所有点，则为true网格图是顶点位于从0,0到n，n的整数坐标处的图。 （所以0,0，0,1，0,2，... 0，n，1,0等）。此外，所有边都在距离1的顶点之间。（所以00-> 01，00-> 10 ，但不能指向其他任何顶点00。此外，某些边可能会丢失。）可以给出多项式时间算法来解决该问题，或者证明该问题是NP-难的。 

所以我想解决旅行推销员的正式声明：输入一个完整的，加权的，有向图G和一个目标整数k如果有一条通过G的路径（1）每次访问...，则输出true。]]

Answer 1

概述：

NP-hard定义了在多项式时间内无法解决的问题。证明问题出在NP上是很简单的-仅表明解决方案在多项式时间内是可验证的-但是，证明问题是NP难的可能会有一点挑战。到目前为止，旅行商问题（TSP）被认为是NP难题（即没有人找到多项式时间解）。