3
$\begingroup$

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

$\endgroup$
  • $\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 '19 at 12:29
  • $\begingroup$ @YuvalFilmus Thx; asked there. $\endgroup$ – user110815 Oct 18 '19 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 '19 at 2:39