Amittai Aviram
CPSC 201 HW 8

Problem 1:

G:

The 7 vertices are ordered 1 to 5 going clockwise from the top vertex
around the outer ring and then 6 and 7 from left to right for the two
inner vertices.

The 9 edges are ordered as follows:

1 - 5
1 - 6
1 - 7
1 - 2
2 - 7
2 - 3
3 - 7
3 - 4
4 - 6
4 - 5
5 - 6

Since we already know that
r1 = y1 = r2 = b2 = y7 = b7 = 0
b1 = y2 = r7 = 1
the vertices of G are represented as follows:

1 (0 + 0 + 1)
2 (0 + 1 + 0)
3 (r3 + y3 + b3)
4 (r4 + y4 + b4)
5 (r5 + y5 + b5)
6 (r6 + y6 + b6)
7 (1 + 0 + 0)

The edges are represented as follows:

1 - 5 (1 + ~r5)(1 + ~y5)(0 + ~b5)
1 - 6 (1 + ~r6)(1 + ~y6)(0 + ~b6)
1 - 7 (1 + 0)(1 + 1)(0 + 1)
1 - 2 (1 + 1)(1 + 0)(0 + 1)
2 - 7 (1 + 0)(0 + 1)(1 + 1)
2 - 3 (1 + ~r3)(0 + ~y3)(1 + ~b3)
3 - 7 (~r3 + 0)(~y3 + 1)(~b3 + 1)
3 - 4 (~r3 + ~r4)(~y3 + ~y4)(~b3 + ~b4)
4 - 6 (~r4 + ~r6)(~y4 + ~y6)(~b4 + ~b6)
4 - 5 (~r4 + ~r5)(~y4 + ~y5)(~b4 + ~b5)
5 - 6 (~r5 + ~r6)(~y5 + ~y6)(~b5 + ~b6)

The product of sums is

(0 + 0 + 1)
 (0 + 1 + 0)
 (r3 + y3 + b3)
 (r4 + y4 + b4)
 (r5 + y5 + b5)
 (r6 + y6 + b6)
 (1 + 0 + 0)
 (1 + ~r5)(1 + ~y5)(0 + ~b5)
 (1 + ~r6)(1 + ~y6)(0 + ~b6)
 (1 + 0)(1 + 1)(0 + 1)
 (1 + 1)(1 + 0)(0 + 1)
 (1 + 0)(0 + 1)(1 + 1)
 (1 + ~r3)(0 + ~y3)(1 + ~b3)
 (~r3 + 0)(~y3 + 1)(~b3 + 1)
 (~r3 + ~r4)(~y3 + ~y4)(~b3 + ~b4)
 (~r4 + ~r6)(~y4 + ~y6)(~b4 + ~b6)
 (~r4 + ~r5)(~y4 + ~y5)(~b4 + ~b5)
 (~r5 + ~r6)(~y5 + ~y6)(~b5 + ~b6)


With all sums removed that already equal 1, the product of sums is

(r3 + y3 + b3)
 (r4 + y4 + b4)
 (r5 + y5 + b5)
 (r6 + y6 + b6)
 (0 + ~b5)
 (0 + ~b6)
 (0 + ~y3)
 (~r3 + 0)
 (~r3 + ~r4)(~y3 + ~y4)(~b3 + ~b4)
 (~r4 + ~r6)(~y4 + ~y6)(~b4 + ~b6)
 (~r4 + ~r5)(~y4 + ~y5)(~b4 + ~b5)
 (~r5 + ~r6)(~y5 + ~y6)(~b5 + ~b6)

H:

We use the same ordering for vertices.  The edges are ordered:

1 - 5
1 - 6
1 - 7
1 - 2
2 - 7
2 - 3
3 - 6
3 - 4
4 - 7
4 - 5
5 - 6

The product of sums is

(r1 + y1 + b1)
 (r2 + y2 + b2)
 (r3 + y3 + b3)
 (r4 + y4 + b4)
 (r5 + y5 + b5)
 (r6 + y6 + b6)
 (r7 + y7 + b7)
 (~r1 + ~r5)(~y1 + ~y5)(~b1 + ~b5)
 (~r1 + ~r6)(~r1 + ~y6)(~b1 + ~b6)
 (~r1 + ~r7)(~r1 + ~r7)(~r1 + ~r7)
 (~r1 + ~r2)(~y1 + ~y2)(~b1 + ~b2)
 (~r2 + ~r7)(~y2 + ~y7)(~b2 + ~b7)
 (~r2 + ~r3)(~y2 + ~y3)(~b2 + ~b3)
 (~r3 + ~r6)(~y3 + ~y6)(~b3 + ~b6)
 (~r3 + ~r4)(~y3 + ~y4)(~b3 + ~b4)
 (~r4 + ~r7)(~y4 + ~y7)(~b4 + ~b7)
 (~r4 + ~r5)(~y4 + ~y5)(~b4 + ~b5)
 (~r5 + ~r6)(~y5 + ~y6)(~b5 + ~b6)

G cannot be colored with three colors.  To see this, note that vertex
4 must be blue.  Therefore, all the vertices in the triangle 4, 5, 6
have an edge with a blue vertex, so their colors must be chosen from
yellow and red.  Since they are connected, they cannot be colored with
only two colors.

H is easy to color, for instance, as follows:

1 blue
2 yellow
3 blue
4 yellow
5 red
6 yellow
7 red

The resulting product-of-sums representation is

(0 + 0 + 1)
 (0 + 1 + 0)
 (0 + 0 + 1)
 (0 + 1 + 0)
 (1 + 0 + 0)
 (0 + 1 + 0)
 (1 + 0 + 0)
 (1 + 0)(1 + 1)(0 + 1)
 (1 + 1)(1 + 0)(0 + 1)
 (1 + 0)(1 + 1)(0 + 1)
 (1 + 1)(1 + 0)(0 + 1)
 (1 + 0)(0 + 1)(1 + 1)
 (1 + 1)(0 + 1)(1 + 0)
 (1 + 1)(1 + 0)(0 + 1)
 (1 + 1)(1 + 0)(0 + 1)
 (1 + 0)(0 + 1)(1 + 1)
 (1 + 0)(0 + 1)(1 + 1)
 (0 + 1)(1 + 0)(1 + 1)

= 1


Problem 2:

By the argument given in Chapter 54, VC is NP-complete, which means
that, if it had a polynomial-time deterministic solution, all other
problems in NP (including the other NP-complete problems) would also
have polynomial-time deterministic solutions.  Now, suppose there were
a polynomial-time transformation f from any instance v of VC to an
instance g of GM that takes time O(p(n)), where n is the size of v and
p is some polynomial, say n^k, where k is a (nonnegative) real number.
We already know (by the hint) that GM has a polynomial-time
deterministic algorithm to solve any instance of it in time
O(n^{2.5}).  Thus a solution to problem v, if f existed, would be the
same (yes or no) as the solution to an instance f(v) of GM, which
would take time O((p(n))^{2.5}) = O(n^{k*2.5}), where n^{k*2.5} is a
polynomial.  But this would imply that there is now a polynomial-time
deterministic algorithm to solve any instance of VC.  Since VC is NP-
complete, this in turn would imply that there must be a deterministic
polynomial-time algorithm to solve any instance of any problem in NP,
which would imply that P = NP, and this contradicts the premise that P
/= NP.


Problem 3:

(a) If I have an algorithm to solve any instance of problem P in time
O(n log n) and a O(n^2) algorithm to reduce any instance of problem P
to an instance of problem Q, this does not give me any information
about how quickly I can solve problem Q.  My reduction helps me to
solve an instance of problem P if I know how to solve any instance of
problem Q, and I don't know whether I know the latter.

(b) Suppose I have a O(n log n) algorithm to solve any instance of Q,
as well as an O(n^2) reduction algorithm f from any instance of
problem P to an instance of problem Q.  To solve instance p of problem
P using the algorithm for Q, I would first transform p to f(p) in
O(n^2) time and then solve f(p) (which is an instance of Q) in O(n log
n) time.  So this would take O(n^2 + n log n) = O(n^2) time.


Problem 4:

In each case, I will prove that the given problem cannot be decided by
reducing an instance of the Halting Problem to an instance of the
given problem.  My motto is this:

  "Well, Jeez!  If I could solve _that_ problem, I could
  solve the Halting Problem!"

Since I know, by means of a logical proof, that i cannot solve the
Halting Problem, this must mean that I also cannot solve the given
problem.

(a)  Create a program L that never halts on any input.  (This is very
easy to accomplish with an endless loop.)  Now take instance h = (P,X)
of the Halting Problem, where P is an arbitrary program and X an
arbitrary input, and submit programs P and L to the decider with input
X.  If the answer is "no," then the answer to h is "yes," because P
has halted while L has not halted.  If the answer is "yes," then the
answer to h is "no," because both L and P have failed to halt.

(b) Let X = Y, i.e., submit two copies of the same input.  Then, if my
decider answers "yes," I have a "yes" answer to the Halting Problem
for program P and input X = Y -- and "no" otherwise.

(c) Take any instance h = (Q,X) of the Halting Problem consisting of
program Q and input X and submit it to my decider.  If my decider's
answer is "no," the answer to the h is "yes."  If the answer from my
decider is "yes," check to see whether the output of Q is 42.  (This
is certainly decidable!)  If so, the answer to h is "yes."  Otherwise,
the answer to h is "no."