I have realized that my problem is that my view of interactive proof systems wrong. I kept thinking of Merlin as a prover and Arthur as a verifier since this is what one reads in the literature. I have realized that it makes more sense to think of Arthur as a skeptic and Merlin as a sly know-it-all, although I should really just stick with the standard Turing machine definitions and not bother with these interpretations.

Would you provide me with a reference where this reduction is shown? It seems that if the circuit is not trivial (in the sense that there are only a couple of satisfying assignments), the output will be FALSE most of the time. But what does this mean? It is not clear to me what the output is supposed to represent in regards to the problem.

Your example is that of a problem in the class AM, correct?

@Tsuyoshi: Yes, I have assummed that Merlin can write down the whole proof. To keep things simple, I do not care about the length of the proof, as long as it is finite.

@Alaggan: Oh, you're right! My mistake.

Nice. I like your idea regarding obstacle (1). I have thought of something similar for obstacle (2), but there is always a problem: Suppose $w$ is of length $k$ and $x$ is of length $n$. Suppose further that the maximum output length $m$ for inputs of length $k$ is the same as that of $n$. Then there is a possibiliy that $C_k(w) = C_n(x)$ but $f(w) \ne f(x)$. Example: $f(w) = 01$, $f(x) = 01 \ 01$, and $C_k(w) = C_n(x) = 01 \ 01 \ 01 \ 01 \ 01$.