# Homework 5

#### Problem 1.

A directed graph is strongly connected if for every pair of
vertices \(u\), \(v\), there is a path from \(u\) to \(v\).

Show that testing whether a given directed graph is strongly connected
is in NL. Then show that it is NL-complete by giving a log-space
reduction from Reachability to StrongConnectedness.

#### Problem 2.

The problem

AcyclicGraph takes as input a directed graph and
answers yes if the graph does not have a directed cycle.

Show that AcyclicGraph is NL-complete.

Hint: What is the negation of this problem? Use the
Immermann-Szelepcsényi Theorem.

#### Problem 3.

Consider a sliding puzzle, like this one, generalized to

\(n\) blocks:

To be more precise, the frame of the puzzle is a rectilinear polygon
(a polygon with horizontal and vertical edges only), all vertices of
which are integers of polynomial size. There are

\(n\) sliding blocks,
which are rectangles of integer side length contained inside the
puzzle frame. We are given an initial position of each block, and a
target position for at least one of the blocks. A move means to
translate a block horizontally or vertically (as far as you want)
without intersecting another block or the frame (touching is allowed).

Show that there is a PSPACE program that prints out the shortest
sequence of moves from the initial configuration to a target
configuration.

Note that the length of the shortest path could be exponential, so we
cannot store it. Instead assume that your program can print out a
move whenever it wishes to. Of course the moves have to be printed in
the correct order.