$1$

CSCI $3110$: Assignment $1(6\%$ of final mark$)$ posted: May $13$th$,2024$

Instructor: Travis Gagie due: $23$:$59$ May $19$th$,2024$

You are allowed to work in groups of up to $3.$ One person in the group is to submit your answers and

a list of all the group members, and each other person in the group is also to submit a list of all the

group members. You can talk with other groups about the normal assignments but, for everything

you write, someone in your group must be able to explain it$.$ If we ask you to explain what you$$ve

written and no one in your group understands it$,$ then it$$s an academic$-$integrity offence.

This assignment is due Sunday night at $23$:$59,$ Halifax time. There are no SDAs for this course.

Late submissions will not be accepted unless you have an accommodation through the Accessibility

Center that allows you to submit work up to $3$ days late, in which case we will accept your

assignment until $23$:$59$ on Wednesday.

$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 $12$ 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\mathrm{.}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 $36=729$ 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?