[tgflynn]

In your post you say that a PSPACE algorithm exists. Do you have a reference for that algorithm ?

Another commenter here is saying the problem has an explicit exponential or worse lower bound.

If both of those claims are true that would prove P != PSPACE, which would be a very important result.