4
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Oct 25, 2019 at 14:15
  • $\begingroup$ @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. $\endgroup$
    – MdAyq
    Oct 25, 2019 at 19:15
  • 2
    $\begingroup$ A couple of examples of considering logspace reductions (1) doi.org/10.1007/s00037-016-0124-0 (2) doi.org/10.1007/978-3-030-29026-9_18 (3) doi.org/10.1007/978-3-030-00250-3_5 $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Oct 29, 2019 at 13:52
  • $\begingroup$ @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? $\endgroup$
    – MdAyq
    Oct 29, 2019 at 15:03

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.