10
$\begingroup$

Is there a way that a prover can convince a verifier that some HORN-SAT expression is satisfiable?

Of course this might seem silly, since there are linear time algorithms for HORN-SAT. On the other hand, HORN-SAT is P-complete, which means it does not have log-space algorithms unless P=L. Accordingly, restrict the computational abilities of the verifier to L. Now the verifier is very feeble, so the problem is no longer silly.

Another twist on this is whether it can be a zero-knowledge proof.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ In the non-zero-knowledge case, I think that the naive verification using a satisfying truth assignment as a certificate requires only log space, provided that the input and the certificate are written on read-only tapes which do not count as space. $\endgroup$
    – Tsuyoshi Ito
    Commented Feb 17, 2011 at 6:50
  • $\begingroup$ @Tsuyoshi: I don't see how to do naive verification in only log-space. If we could, wouldn't that show HORN-SAT is in NL, and thus by P-completeness give P = NL? $\endgroup$
    – Shaun Harker
    Commented Feb 17, 2011 at 17:46
  • $\begingroup$ No. I assumed the certificate is on a read-only tape, which is different from verification performed by NL. $\endgroup$
    – Tsuyoshi Ito
    Commented Feb 17, 2011 at 17:57
  • $\begingroup$ @Tsuyoshi: Ah, so you can read the certificate many times, whereas a certificate-based definition of NL would have a certificate which can only be read once. $\endgroup$
    – Shaun Harker
    Commented Feb 18, 2011 at 2:37

1 Answer 1

Reset to default
11
$\begingroup$

This http://www.cs.ubc.ca/~condon/papers/ips-survey.pdf survey by Anne Condon contains many facts about space bounded interactive proof systems.

There are several models, and the main differences are whether you allow private coins for the verifier (IP) or public coins only (AM), and whether you also restrict the verification time to polynomial (not implied by the space bound alone).

Without the time restriction the answer is yes: IP(log-space) contains EXP and AM(log-space)=P.

Note that IP(log-space) is most likely larger than standard IP. On the other hand IP(log-space, poly-time)=IP=PSPACE.

AM(log-space, poly-time) = P due to 'Delegating Computation: Interactive Proofs for Muggles' by Goldwasser et al., STOC 2008.

Furthermore the paper 'Zero knowledge with log-space verifiers' by Kilian (FOCS 88) shows how to get a log-space poly-time zero knowledge proof system for everything in IP (with private coins obviously).

Improve this answer
$\endgroup$
2

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.