# 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 ?
\]

- Prove that Partition is NP-hard by a reduction from
SubsetSum.
- 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.

- Describe a polynomial-time algorithm to solve DNF-SAT.
- 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!