We have a composition logspace computable functions where the outer machine is one-way and the inner is a logspace verifier with a read at once certificate tape and output string (instead of "yes" or "no" answers). One of my colleague told me it is obligated to recompute the certificate tape since for this composition, you need to read the certificate many times, and thus does not work, since it is on a oneway tape and I am saying that it is not necessary and this actually never happens because the outer machine is one-way.

I want to know if my explanation is (almost) correct or I am (partially) wrong and maybe some pieces of advice or verifiable facts to deal with that person which I'm trying to convince him (Thanks in advance), please.


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.