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.
Show that AcyclicGraph is NL-complete.
Hint: What is the negation of this problem? Use the Immermann-Szelepcsényi Theorem.
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.