In general, how can I verify that my many-one reduction is a LogSpace reduction? E.g. I was looking at the proof of HORN-SAT is P-complete via logspace reduction.

It would be ok even if someone makes me a simple example of LogSpace reduction clearly explaining why it is LogSpace and not polynomial.

Many thanks.

  • $\begingroup$ Every logspace reduction is polynomial. $\endgroup$ Nov 14 '21 at 6:55
  • $\begingroup$ @YuvalFilmus Yes, I meant just polinomial. E.g. a polynomial time reduction would not be ok for proving HORN-SAT is P-complete, right? $\endgroup$
    – Abel Freid
    Nov 14 '21 at 10:04
  • $\begingroup$ If the reduction can be implemented so that is uses only logarithmic space, then it is logspace. $\endgroup$ Nov 14 '21 at 11:52

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.