$1$

$.$

$$Give a diagonalization showing that it is impossible to approximate the Kolmogorov Com

$-$

plexity to within a factor of

$2$

$.$

$($

Hint: Modify the diagonalization in the lecture notes.

$)$

$2$

$.$

$$Write a propositional

$-$

logic formula F on the

$1$

$2$

$$variables Vr

$,$

$$Vg

$,$

$$Vy

$,$

$$Ir

$,$

$$Ig

$,$

$$Iy

$,$

$$Rr

$,$

$$Rg

$,$

$$Ry

$,$

$$Cr

$,$

$$Cg

$,$

$$Cy

such that there is a bijection between the satisfying truth assignments for F and the valid

$3$

$-$

colourings with the colours red, green and yellow of the

$4$

$$counties of Cape Breton Island.

Sketch that bijection.

$3$

$.$

$$Show that Binary Integer Linear Programming

$($

BILP

$)$

$$is NP

$-$

complete by

$$

$$showing that you can check an alleged solution in polynomial time,

$$

$$giving a polynomial

$-$

time reduction from Independent Set to BILP.

Given a graph G

$,$

$$your reduction should return a BILP instance whose objective function has

value at least k if and only if G has an independent set of size at least k

$.$

$4$

$.$

$$Apply your reduction to the graph in Figure

$2$

$.$

$3$

$$in the lecture notes.

$($

If you just write any

old BILP instance whose objective function has value at least

$4$

$$because you can see there is

an independent set of

$4$

$$vertices$,$ then you won

$$

t have applied a reduction and you

$$

ll get

$0$

$.$

$)$

$5$

$.$

$$Suppose you want to prove to your friend have a solution to an instance of an NP

$-$

complete

problem X

$,$

$$but you don

$$

t want to tell them the solution. How can you use the zero

$-$

knowledge

proof of knowledge for

$3$

$-$

Col to do this?

$($

Hint: Use the fact that

$3$

$-$

Col is NP

$-$

complete.

$)$

$6$

$.$

$$Give an algorithm that, given a connected graph G on n vertices with n

$+$

$5$

$$edges for some

constant c

$,$

$$finds a minimum

$-$

size vertex cover for G in O

$($

n

$)$

$$time$.$

$($

Hint: Use BFS or DFS to

select a subgraph of G that

$$

s a tree on n vertices and consider the

$6$

$$leftover edges that aren

$$

t

in that tree; consider how you could cover those

$6$

$$edges

$$

$$for each, take one end, take other

or take both

$$

$$and think about what to do for each of the at most

$3$

$6$

$=$

$7$

$2$

$9$

$$possibilities$.$

$)$

Bonus: To show a problem X is NP

$-$

complete,

$1$

$)$

$$we show X can be solved on an NP Turing machine

and

$2$

$)$

$$we reduce a know NP

$-$

complete problem to X

$($

thus showing we can program an

NP Turing machine in X

$)$

$.$

$$When we show a programming language Y is Turing

$-$

complete,

however, we just show we can program a Turing machine in Y ; why don

$$

t we show that Y

can be interpreted on a Turing machine?