TCS3 Assignment
Check DUO for the submission deadline.
You must reference any sources used. Please keep submit your solutions in a single pdf
file.
Full justification is required in each solution. The marks available for correct answers to
each question are indicated. Partial credit will be given for good attempts.
Complexity and Approximability
Question 1
Let Short Path be the following problem:
Instance: An undirected graph G, two vertices s, t in it and a number k > 0.
Question: Does G have a path from s to t of length at most k?
Let Short Path-2019 be the same problem as above, but with k ≤ 2019.
1. Show that Short Path is NL-complete. [25 marks]
2. Show that Short Path-2019 belongs to the complexity class L. [5 marks]
Question 2 [20 marks]
Let Two Cliques be the following problem:
Instance: An undirected graph G = (V,E).
Question: Are there two disjoint non-empty subsets V1 and V2 in V such that V = V1 ∪ V2
and each Vi is a clique?
It is obvious that Two Cliques is in NP, so it cannot be PSPACE-complete, assum-
ing that NP 6= PSPACE. However, it is open whether NP 6= PSPACE. Prove un-
conditionally (i.e. without using any unproven assumptions) that Two Cliques is not
PSPACE-complete with respect to logspace reductions.
Algorithmic Game Theory
Question 3
A community of n ≥ 3 people benefit from a piece of work that could be completed by
two or more volunteers. They receive payoffs that are the same for every member and are
as follows.
1. If you volunteered, you get 9.
2. If you didn’t volunteer but the work was done by others, you get 10.
3. If you didn’t volunteer and the work wasn’t done (because fewer than two others
volunteered), you get 8.
Find all pure-strategy equilibria. [10 marks]
Find all symmetric mixed-strategy equlibria (i.e. the ones where all players have the
same mixed strategy). For this part, determining the probability for volunteering as the
solution of e.g. some polynomial equation is OK, in which case you may need to argue
that such a solution exists. [25 marks]
Question 4 [15 marks]
Show that a Boolean function f (p1, p2) can be computed by a three-player game. That
is, each player has two pure strategies that are the Boolean values T and F , and there’s
a pure-strategy Nash equilibrium if and only the strategy of player three, p3 = f (p1, p2)
where p1and p2 are the strategies of players one and two, respectively.
2