Proof for NP hard or P equation below

Question

So I want to solve
The formal statement of Traveling Salesman:
Input a complete, weighted, directed graph G, and a target integer k
Output true if there is a path through G that

1) visits every vertex exactly once
2) costs <= k

With:
Input: a directed grid graph G, a set of target points S, and an integer k Output: true if there is a path through G that visits all points in S using at most k left turns
A grid graph is a graph where the vertices are at integer coordinates from 0,0 to n,n. (So 0,0, 0,1, 0,2, ...0,n, 1,0, etc.) Also, all edges are between vertices at distance 1. (So 00->01, 00->10, but not 00 to any other vertex. Also some edges could be missing.)
Either give a polynomial-time algorithm to solve this problem, or prove this problem is NP-hard.

Answer 1

Overview: NP-hard defines problems that cannot be solved in polynomial time. It is quite trivial to prove that a problem is in NP - simply show that solutions are verifiable in polynomial time - however, proving a problem is NP-hard can be slightly challenging. As of now, the traveling salesman problem (TSP) is considered to be NP-hard (i.e. nobody has found a polynomial time solution).

How to prove: Proving NP-hard requires showing that every problem y in NP can be reduced to TSP in polynomial time. To do this, we typically demonstrate that there is a polynomial time transformation of the problem to SAT (Boolean Satisfiability). For this problem, we will instead show that HC (Hamiltonian Cycle) can reduce to TSP in polynomial time. Since HC is universally accepted as an NP-complete problem, showing this reduction will prove that TSP is NP-hard.

The proof:

HC Reduction: G = (V, E). Let k = |V| = n (# of nodes in G), and set all edge weights to one. Set weight of edges not originally in G to two, in order to account for our incomplete graph). Input this modified graph into the TSP described above, and ask if there is a tour on G with cost less than or equal to k.

Proof of correctness: This can be done by parts, since there are two possible solutions for each algorithm.

1. If HC returns True, then TSP returns True - If HC returns true, then there exists a simple cycle with n edges (satisfies condition #1, per your question). Each edge has weight one, the overall tour has cost n. Therefore, since k = n (satisfies condition #2), TCP will also return true. QED.

2. If HC returns False, then TSP returns False - By contradiction, let's suppose TSP returns true. HC returning false implies there does not exist a simple cycle with n edges. Since k = n and we assume TSP returns true, that means every edge traversed has weight one, and subsequently must be edges in the HC graph. Note that traversing these corresponding edges in HC forms a simple cycle, which is a contradiction. QED.