New answers tagged

3

Your proof that the problem is in PSPACE is not quite correct. The problem is that the product $n_1 \cdots n_k$ is not bounded by a polynomial in the input length $n_1 + \dots + n_k$. The correct way to do it is to directly apply Savitch's theorem to the NPSPACE machine that nondeterministically guesses a path through the product graph. The difference is ...


Top 50 recent answers are included