Continuing Is every PSPACE-complete problem complete with respect to logspace reductions? : earlier, PSPACE-completeness was defined via logspace reductions (e.g., cf. http://www.cs.cornell.edu/~kozen/Papers/LowerBounds.pdf), whereas it is defined via ptime reductions nowadays (e.g., cf. https://en.wikipedia.org/wiki/PSPACE).

Why has it changed? Is it just because the folks after Dexter Kozen got too lazy even to say that one can go the extra mile to show that their reductions are actually logspace, let alone actually going that extra mile? Or is there a deeper, technical reason?

Crosspost: http://cstheory.stackexchange.com/questions/45709/logspace-reductions-vs-ptime-reductons-for-defining-pspace-completeness


closed as off-topic by D.W. Oct 18 at 2:39

  • This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ This is to some extent arbitrary, and may require a historical investigation. For this reason, perhaps it's better to ask this on the "grown up" site Theoretical Computer Science. $\endgroup$ – Yuval Filmus Oct 17 at 12:29
  • $\begingroup$ @YuvalFilmus Thx; asked there. $\endgroup$ – user110815 Oct 18 at 0:29
  • $\begingroup$ I'm voting to close this question because it was posted on CSTheory, and we don't allow simultaneous cross-posting. $\endgroup$ – D.W. Oct 18 at 2:39