<p>Continuing <a href="https://cs.stackexchange.com/questions/90527/is-every-pspace-complete-problem-complete-with-respect-to-logspace-reductions">https://cs.stackexchange.com/questions/90527/is-every-pspace-complete-problem-complete-with-respect-to-logspace-reductions</a> : earlier, PSPACE-completeness was defined via logspace reductions (e.g., cf. <a href="http://www.cs.cornell.edu/~kozen/Papers/LowerBounds.pdf" rel="nofollow noreferrer">http://www.cs.cornell.edu/~kozen/Papers/LowerBounds.pdf</a>), whereas it is defined via ptime reductions nowadays (e.g., cf. <a href="https://en.wikipedia.org/wiki/PSPACE" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/PSPACE</a>).</p>

<p>Why has it changed? Is it just because the folks after Dexter Kozen got too lazy even to <strong>say</strong> 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?</p>

<p>Crosspost: <a href="http://cs.stackexchange.com/questions/115921/logspace-reductions-vs-ptime-reductons-for-defining-pspace-completeness">http://cs.stackexchange.com/questions/115921/logspace-reductions-vs-ptime-reductons-for-defining-pspace-completeness</a></p>

CC BY-SA 4.0
2019-10-25T14:15:33.947Z
It’s not *earlier* vs. *nowadays*. It’s just that different works use different conventions. In particular, for an introductory text such as a Wikipedia article there is an incentive to use the most simple definitions, whereas in a research paper there is an incentive to use definitions that make the results as strong as possible.
Emil Jeřábek
CC BY-SA 4.0
2019-10-25T19:15:34.553Z
@EmilJeřábek I am not aware of *recent* publications in which PSPACE-completeness is defined via logspace reductions. E.g., "Introduction to the Theory of Computation" by Sipser (3rd ed.) and "Introduction to automata theory, languages, and computation" by Hopcroft/Motwani/Ullman, 2001 use polytime reductions.
MdAyq
CC BY-SA 4.0
2019-10-29T13:52:22.253Z
A couple of examples of considering logspace reductions (1) https://doi.org/10.1007/s00037-016-0124-0 (2)
https://doi.org/10.1007/978-3-030-29026-9_18 (3) https://doi.org/10.1007/978-3-030-00250-3_5
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2019-10-29T15:03:37.473Z
@KristofferArnsfeltHansen Good to know. Thank you! I was surprised to discover that reductions for PSPACE exist that I was not aware of earlier (e.g., ZPP reductions). What would be the best source to catch up?
MdAyq
<reductions><pspace>
LogSpace reductions vs. PTime reductons for defining PSpace-completeness
MdAyq
# LogSpace reductions vs. PTime reductons for defining PSpace-completeness

(Asked by: username_0 on 2019-10-18)

Continuing <https://cs.stackexchange.com/questions/90527/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://cs.stackexchange.com/questions/115921/logspace-reductions-vs-ptime-reductons-for-defining-pspace-completeness>

**Tags:** reductions, pspace
> **Comments:**
> **username_1**: It’s not *earlier* vs. *nowadays*. It’s just that different works use different conventions. In particular, for an introductory text such as a Wikipedia article there is an incentive to use the most simple definitions, whereas in a research paper there is an incentive to use definitions that make the results as strong as possible.  
> **username_0**: @EmilJeřábek I am not aware of *recent* publications in which PSPACE-completeness is defined via logspace reductions. E.g., "Introduction to the Theory of Computation" by Sipser (3rd ed.) and "Introduction to automata theory, languages, and computation" by Hopcroft/Motwani/Ullman, 2001 use polytime reductions.  
> **username_2**: A couple of examples of considering logspace reductions (1) https://doi.org/10.1007/s00037-016-0124-0 (2) https://doi.org/10.1007/978-3-030-29026-9_18 (3) https://doi.org/10.1007/978-3-030-00250-3_5  
> **username_0**: @KristofferArnsfeltHansen Good to know. Thank you! I was surprised to discover that reductions for PSPACE exist that I was not aware of earlier (e.g., ZPP reductions). What would be the best source to catch up?  

---

## 0 answers

