<p>Consider usual interactive proofs (Arthur is polynomial-time bounded and can use random bits)</p>
<p>where computation power of Merlin is bounded by polynomial-size circuits.</p>
<p>For example, every unary NP-language can be decided in the corresponding model. (There exists a poly(<span class="math-container">$n$</span>)-size circuit that on input <span class="math-container">$1^n$</span> outputs a certificate if it exists.)</p>
<p>Are there any researches about this model?</p>

CC BY-SA 4.0
2022-09-11T13:42:35.350Z
Do you mean that for every string in the language, there exists a circuit implementing Merlin for this particular input, or do you require one circuit for each input length whose inputs include the original input? In the former case, the class you get is MA, in the latter case it's oblivious MA.
Emil Jeřábek
CC BY-SA 4.0
2022-09-11T15:39:43.410Z
@EmilJeřábek, I mean one circuit with size poly($n$) for all inputs of length $n$.
I do not understand how to get MA...
Alexey Milovanov
CC BY-SA 4.0
2022-09-11T17:04:11.137Z
Oblivious MA, then. The point is that all Merlin needs to do is send his circuit; then Arthur can simulate it himself without further interaction.
Emil Jeřábek
CC BY-SA 4.0
2022-09-11T18:57:27.387Z
@EmilJeřábek Could you please explain what is ``Oblivious MA" or give a reference?
Alexey Milovanov
CC BY-SA 4.0
2022-09-11T19:39:57.110Z
https://complexityzoo.net/Complexity_Zoo:O#oma
Emil Jeřábek
CC BY-SA 4.0
2022-09-13T07:33:56.063Z
You might want to look at Section 3 in the following paper:
https://eccc.weizmann.ac.il/report/2011/023/
Or Meir
<cc.complexity-theory><complexity-classes><interactive-proofs>
Interactive proofs with computation bounded Merlin
Alexey Milovanov
# Interactive proofs with computation bounded Merlin

(Asked by: username_0 on 2022-09-11)

Consider usual interactive proofs (Arthur is polynomial-time bounded and can use random bits)

where computation power of Merlin is bounded by polynomial-size circuits.

For example, every unary NP-language can be decided in the corresponding model. (There exists a poly($n$)-size circuit that on input $1^n$ outputs a certificate if it exists.)

Are there any researches about this model?

**Tags:** cc.complexity-theory, complexity-classes, interactive-proofs

> **Comments:**
> **username_1**: Do you mean that for every string in the language, there exists a circuit implementing Merlin for this particular input, or do you require one circuit for each input length whose inputs include the original input? In the former case, the class you get is MA, in the latter case it's oblivious MA.  
> **username_0**: @EmilJeřábek, I mean one circuit with size poly($n$) for all inputs of length $n$. I do not understand how to get MA...  
> **username_1**: Oblivious MA, then. The point is that all Merlin needs to do is send his circuit; then Arthur can simulate it himself without further interaction.  
> **username_0**: @EmilJeřábek Could you please explain what is ``Oblivious MA" or give a reference?  
> **username_1**: https://complexityzoo.net/Complexity_Zoo:O#oma  
> **username_2**: You might want to look at Section 3 in the following paper: https://eccc.weizmann.ac.il/report/2011/023/  

---

## 0 answers

