I asked the following question on math.se but it wasn't really answered so moved it over here as I feel it's more relevant.
I saw the question below on an old stack exchange question when looking to understand NP-completeness. At first, I thought I understood it so I gave it a go but ended up more confused than before (I'm a maths student and computational complexity is my first foray into CS and I'm struggling to get to grips with it).
Question is as below:
Given as inputs integers $a, b$ and $c(i,j)$ for each $i,j \leq a$, decide if there is a permutation $\tau$ of $\{1,2,\dots,a\}$ such that
$$ c(\tau(a),\tau(1))+\sum_{i=1}^{a-1}c((\tau(i),\tau(i+1))\leq b $$
Prove this problem is NP-complete. Hint: find a reduction from the Hamiltonian circuit decision problem (given a graph, decide whether it contains a Hamiltonian circuit).
It seems very similar to the decision version of TSP (where given a set of cities with the distances between each pair of cities, and a length $k$, does there exist a circuit connecting all cities of length less than $k$). I've read the proof for NP-completeness of TSP and I feel like I understand the reduction from Hamiltonian circuit decision problem to TSP, but I can't get it to translate into a reduction from HC to this problem.
My understanding to compare this to TSP, is that $a$ is the number of cities, each $c(i,j)$ represents the distance between city $i$ and $j$.
My (fairly poor) attempt at this reduction is as follows;
The problem is clearly in NP as we can non-deterministically "guess" a permutation and calculate the given sum and verify that it's at most $b$ in polynomial time.
Then, given a graph $G=\langle V,E\rangle$ where there are $a$ vertices, say $1,2,\ldots,a$, and $b$ edges of length $c(i,j)$, where $i \neq j$ and $i,j\leq a$, construct the completion of $G'$ of $G$ and a weight function that assigns any edge of $G'$ a 1 if the edge is present in $G$ and 2 if not. This can be computed in polynomial time.
Then if $G$ contains a Hamiltonian circuit (consisting of $b$ edges), this path has weight at most $b$ in $G'$ and so the sum of the lengths of this path is at most $b$ and so the permutation corresponding to the order of this path satisfies the original decision problem for these numbers $a,b$ and $c(i,j)$.
Conversely, if given the numbers $a,b$ and $c(i,j)$ and a permutation $\tau$ that satisfy the problem the associated graph G contains a path starting at $\tau(a)$ and finishing at $\tau(b)$. Thus G has a Hamiltonian circuit.
Thus HC reduces to this problem and hence it is NP-hard and so NP-complete.
I can tell it's wrong but I'm not sure how to properly describe a function relating to Hamiltonian circuits and lengths into weights in $G'$.
Any advice and or pointers would be much appreciated.
