0
$\begingroup$

Prove that problem $A$ is complete in $P$ due to reductions computed in logarythmic space

How to understand this statement ? What should be shown ? For me:
1. $A$ is in $P$.
2. Each problem in $P$ can be reduced in logspace to $A$

Can I use transitivity of logspace in this exercise ?

$\endgroup$
  • $\begingroup$ Your understanding of the definition of "complete with respect to reductions computed in logarithmic space" is correct. $\endgroup$ – Yuval Filmus Aug 13 '17 at 3:15
  • $\begingroup$ As to your other question, whether you can use transitivity of logspace in this exercise, this is a question to whoever gave you the exercise; we cannot possibly answer it. In published math you are allowed (and encouraged) to use whatever correct facts you can cite. $\endgroup$ – Yuval Filmus Aug 13 '17 at 3:16
  • $\begingroup$ Question contains complete answer; voting to close. $\endgroup$ – Yuval Filmus Aug 13 '17 at 3:17
  • $\begingroup$ @YuvalFilmus I meant: Can I use trick similar to logspace transitivity ? Some machine $C$ capture readings from tape (field $i$) of machine $K$ and in logspace provides field $i$. So the difference is that here $K$ works in $P$, no logspace. Is it also ok in this case use this trick ? $\endgroup$ – Haskell Fun Aug 13 '17 at 7:01
  • $\begingroup$ You need to give a logspace reduction from a P-complete problem (with respect to logspace reductions) to A. $\endgroup$ – Yuval Filmus Aug 13 '17 at 12:55

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.