We all know the algorithm that solves the Generalized Geography problem using polynomial space (it's described on wiki). My question is: what is the time complexity of this algorithm? I'd like a more precise answer than just 'polynomial'. As far as I understand, we're making $|V|$ calls at most? We won't call the function from the same node more than once because nodes are deleted once visited. And we also have to estimate how much does one iteration take, which, I assume, would be $O(|E|)$ since we're going through all vertices connected to the current one? So that would make the overall time complexity $O(|V|\cdot|E|)$.

I'm also curious about exact space complexity, not just 'polynomial' (I can see that), but something precise like $O(|V|^2)$. If I understand correctly, recursion depth in $O(|V|)$, would that mean that overall space complexity is $O(|V|)$ or am I missing something here?

  • $\begingroup$ GG is PSPACE-complete, so, algorithm is exponential. $\endgroup$ – rus9384 Mar 19 '18 at 7:37
  • $\begingroup$ @rus9384 could you please elaborate on that? I don't see the connection. I know that PSPACE in contained in EXPTIME, but I'd like to know precisely why this algorithm is exponential because I can't analyze the running time correctly myself. $\endgroup$ – wubwubnoobnoob Mar 19 '18 at 7:45
  • $\begingroup$ Given algorithm requires exponential time, but it's unknown if best algorithm requires superpolynomial time. It is open problem if P = PSPACE. The difference between EXP is that EXP-hard problems are thought to require exponential space. Unproved, though. $\endgroup$ – rus9384 Mar 19 '18 at 7:51
  • $\begingroup$ @rus9384 thank you for your explanations about complexity classes! But I'm currently interested in why exactly the given algorithm requires exponential time, nothing else. Just the time complexity analysis of this algorithm. $\endgroup$ – wubwubnoobnoob Mar 19 '18 at 8:01
  • 1
    $\begingroup$ @rus9384 OK, but a flat claim that the algorithm is exponential, without even looking at it, isn't really useful. This is part of the reason we don't post answers as comments: bad comments can't be downvoted. $\endgroup$ – David Richerby Mar 19 '18 at 9:19

Your Answer

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

Browse other questions tagged or ask your own question.