<p>This <a href="http://www.cs.ubc.ca/~condon/papers/ips-survey.pdf" rel="nofollow">http://www.cs.ubc.ca/~condon/papers/ips-survey.pdf</a>
survey by Anne Condon contains many facts about space bounded interactive proof systems.</p>

<p>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).</p>

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

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

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

<p>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).</p>

CC BY-SA 2.5
2011-02-18T02:47:42.140Z
I've also found a paper entitled [Delegating Computation: Interactive Proofs for Muggles](http://www.mit.edu/~rothblum/papers/delegation.pdf). Does Theorem 3 of this work show that AM(log-space, poly-time) = P?
Shaun Harker
CC BY-SA 2.5
2011-02-18T11:18:33.690Z
Yes,they indeed show that!
Hartmut Klauck
CC BY-SA 2.5
2011-02-17T06:57:22.017Z
2011-02-18T11:20:49.960Z
2011-02-18T11:20:49.960Z
Hartmut Klauck
<p>Is there a way that a prover can convince a verifier that some HORN-SAT expression is satisfiable?</p>

<p>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.</p>

<p>Another twist on this is whether it can be a zero-knowledge proof.</p>

CC BY-SA 2.5
2011-02-17T06:50:06.897Z
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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-17T17:46:46.553Z
@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?
Shaun Harker
CC BY-SA 2.5
2011-02-17T17:57:52.620Z
No.  I assumed the certificate is on a read-only tape, which is different from verification performed by NL.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-18T02:37:54.383Z
@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.
Shaun Harker
<cc.complexity-theory><interactive-proofs><zero-knowledge>
Interactive Proof for HORN-SAT?
Shaun Harker
# Interactive Proof for HORN-SAT?

(Asked by: username_0 on 2011-02-17)

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.

**Tags:** cc.complexity-theory, interactive-proofs, zero-knowledge
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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?  
> **username_1**: No.  I assumed the certificate is on a read-only tape, which is different from verification performed by NL.  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_2 on 2011-02-17. Score: 11 | Accepted answer

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).

> **Comments:**
> **username_0**: I've also found a paper entitled [Delegating Computation: Interactive Proofs for Muggles](http://www.mit.edu/~rothblum/papers/delegation.pdf). Does Theorem 3 of this work show that AM(log-space, poly-time) = P?  
> **username_2**: Yes,they indeed show that!  

---

