The jth element of the vector Ax has the form Σ a_jkx_k, where k ranges over all variables. It's natural to relate this to the truth value of the jth clause. The inequality constraint of the given problem suggests that we want to make this sum small in those cases where there is a satisfying assignment. This in turn suggests that we want to give a_jkx_k a relatively low value when the truth assignment of x_k helps to satisfy the clause, and a high value otherwise. So variables that appear negated in the clause should get positive coefficients (to help give a large sum when x_k = 1), and variables that appear unnegated should get a negative coefficient (to help give a small sum when x_k = 1). Since the truth values of variables that do not appear in the clause don't affect satisfiability, it seems best to let the corresponding a_jk's have the value 0.

The simplest guess would be to let a_jk have value 1 if x_k appears negated in clause j, value -1 if it appears unnegated in clause j, and value 0 if it does not appear in clause j. Note that this choice of the a_jk values is independent of the assignment of truth values. In fact, this choice of the a_jk can be made to work.

The expression Σ a_jkx_k would then have value equal to the number of variables which were assigned the value true, but appear negated in the clause. For a nonsatisfying assignment, this would be the total number n_j of variables that appear negated in the clause. Any other assignment to the variables that appear in the clause would have to satisfy the clause, and would have to give a smaller sum. This last claim can be seen to be true by seeing what happens to the sum when the nonsatisfying assignment is modified (for one of the variables appearing in the clause). If the assignment of x_k is changed from 1 to 0, then a_jk would be have to be +1 to make the original assignment nonsatisfying, so the term a_jkx_k becomes smaller by 1. And if the assignment of x_k is changed from 0 to 1, then a_jk would be have to be -1 to make the original assignment nonsatisfying, so the term a_jkx_k again becomes smaller by 1.

We have shown that if we define the entries a_jk as suggested above, the jth element of the vector Ax has the value n_j if the assignment represented by x does not satisfy clause j, and has a smaller value if it does. So defining the vector b to have its jth element equal to n_j - 1 would mean that Ax <= b iff no clause is unsatisfied by the assignment represented by x. In other words, the corresponding instance of the new problem is equivalent to the original instance of 3-SAT.

Note that computing A and b requires only O(mn) work. If the variables are listed explicitly in the representation of an instance of 3-SAT, both m and n are less than the input size. If they are not, then we may assume that n is no greater than the number of variables in the m clauses (which cannot exceed 3m), so that n is O(m), and m is less than the input size. In either case, the work required takes time polynomial in the input size.

1. The minimum cost spanning tree contains the edges {0,2}, {2,3}, and {2,4} of cost 10, and the edges {0,1} and {4,5} of cost 14, for a total cost of 58.

2. The given policy gives a tour that visits the vertices in the order 0,1,0,2,3,2,4,5,4,2,0, corresponding to the tour (0 1 2 3 4 5 0). The cost of this tour is 14 + 22 + 10 + 14 + 14 + 31 = 105.

3. Starting the tour at vertex 1 would visit the vertices in the order 1,0,2,3,2,4,5,4,2,0,1, corresponding to a tour (1 0 2 3 4 5 1). The cost of this tour is 14 + 10 + 10 + 14 + 14 + 40 = 102. Other starting vertices may also give shorter tours.

4. Starting the tour at vertex 0 would now be consistent with visiting the vertices in the order 0,2,4,5,4,2,3,2,0,1,0, corresponding to a tour (0 2 4 5 3 1 0). The cost of this tour is 10 + 10 + 14 + 20 + 20 + 14 = 88. This is in fact the cheapest tour. Other orders of visitation may also give shorter tours.

5. It's possible to have a TSP instance where the minimum spanning tree contains a vertex v of degree n-1, where n is the number of vertices. In this case, all of the (n-1)! tours beginning at v are considered, while for every other vertex w, all of the (n-2)! tours beginning with w and v are considered. So (n-1)! + (n-1)(n-2)! = 2(n-1)! tours are considered in all. Note that this strategy is worse than the naive strategy for getting an exact solution, since it doesn't take advantage of the rotational symmetry that lets us start a cycle with any vertex.

Grading scale: 36 A, 34 A-, 32 B+, 28 B, 26 B-, 24 C+, 20 C