Homework 1

Problem 1.

In this problem we study the top-to-random shuffle which is the following Markov chain. There is a deck of \(n\) distinct cards. A state is a permutation or ordering of the \(n\) cards. At each time, take the top-most card and randomly choose one of the \(n\) possible positions for the card.

For example, suppose we have \(n=8\) cards and they are labeled \(1,2,...,8\). Say at time \(t=3\) we are at the ordering \(3,4,1,8,6,7,5,2\). The top card is card \(2\). There are \(8\) possible locations for it:

before 3, between 3 and 4, between 4 and 1, ..., between 7 and 5, and after 5.

Choose randomly from these \(8\) possibilities. Say we chose to place it between \(4\) and \(1\). Then our new state at time \(t=4\) is the ordering \(3,4,2,1,8,6,7,5\). And we repeat the process with card \(5\) now being the top-card.

(a) Is this Markov chain ergodic? Prove your answer!

(b) Prove that the uniform distribution over all \(n!\) orderings is a stationary distribution.

Problem 2.

Show that the problem of deciding whether an unweighted directed graph has a path of length greater than \(k\) is NP-Complete.

Problem 3.

Partition is the following problem: Given a set \(S\) of \(n\) positive integers, are there subsets \(A\) and \(B\) such that \(A \cup B = S\), \(A \cap B = \emptyset\), and
\[ \sum_{a \in A} a = \sum_{b \in B} b ? \]
  1. Prove that Partition is NP-hard by a reduction from SubsetSum.
  2. Show a polynomial-time reduction from Partition to SubsetSum.

Problem 4.

Let \(G = (V, E)\) be a graph. A dominating set in \(G\) is a subset \(S\) of the vertices such that every vertex in \(G\) is either in \(S\) or adjacent to a vertex in \(S\). The DominatingSet problem asks, given a graph \(G\) and an integer \(k\) as input, whether \(G\) contains a dominating set of size \(k\). Prove that this problem is NP-complete.

Problem 5.

A boolean formula is in disjunctive normal form (or DNF) if it consists of a disjunction (OR) of several terms, each of which is the conjunction (AND) of one or more literals. For example, the formula

\[ ( \lnot x \land y \land \lnot z ) \lor ( y \land \lnot z ) \lor ( x \land \lnot y \land \lnot z ) \]
is in disjunctive normal form. DNF-SAT asks, given a boolean formula in disjunctive normal form, whether that formula is satisfiable.
  1. Describe a polynomial-time algorithm to solve DNF-SAT.
  2. What is the error in the following argument that P = NP?
    Suppose we are given a boolean formula in conjunctive normal form with at most three literals per clause, and we want to know if it is satisfiable. We can use the distributive law to construct an equivalent formula in disjunctive normal form. For example,
    \[ (x \lor y \lor \lnot z) \land (\lnot x \lor \lnot y) \Longleftrightarrow (x \land \lnot y) \lor (y \land \lnot x) \lor (\lnot z \land \lnot x) \lor (\lnot z \land \lnot y) \]
    Now we can use the algorithm from part (1) to determine, in polynomial time, whether the resulting DNF formula is satisfiable. We have just solved 3SAT in polynomial time. Since 3SAT is NP-hard, we must conclude that P=NP!