2
$\begingroup$

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 ?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.