[Solved]: If a problem is PSPACE-complete what do we know about NL-completeness

Problem Detail: 

I have a problem $A$ which was shown to be PSPACE-complete by reduction from planning. However, $A$ can also be transformed into reachability problem which is NL-complete.

I know that $NL=NSPACE(log \ n)$ and $PSPACE=NSPACE$.

Does this mean $A$ is also NL-complete? IF yes, does it make any difference in this context to say whether $A$ is PSPACE-complete or NL-complete ?

Asked By : seteropere

Answered By : Yuval Filmus

A PSPACE-complete problem cannot be in NL, and in particular cannot be NL-complete (this is a consequence of the space hierarchy theorem). However, it is NL-hard. If $A$ can be transformed into a reachability problem, then probably the transformation is not polynomial-time.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19373

3.2K people like this

 Download Related Notes/Documents