# 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.