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

  • 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 '19 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 '19 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 '19 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 '19 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.