I'm struggling to understand a question I've been given. The question asks: Let $\psi$ be a boolean formula in $n$ variables. There are $2^n$ different combinations of assigning values to the variables. Consider the problem of deciding whether (strictly) more than $2^{n−1}$ of these assignments satisfy the formula $\psi$. We will call the language that corresponds to this decision problem, $L$.

From this I can tell that if $x_1, x_2, ..., x_n$ are the $n$ variables which can be either true or false. I understand why there would be $2^n$ different assignings for the formula, as each variable can be assigned 1 of 2 values. But then what is $\psi$ exactly, is it an assignment such as $\psi$=($x_1 \lor x_2 \lor ... x_n$). But then the later part of the question doesn't make any sense. Can someone please explain in more detail what it means by "deciding whether (strictly) more than $2^{n−1}$ of these assignments satisfy the formula $\psi$"?

The question is then to show that there exists a turing machine $M$ and polynomials $T$ and $p$, with the following properties:

• For every input $x$, $M$ terminates after at most $T(|x|)$ steps.

• If $x\in L$, then $Pr_{t∈\small\{0,1\small\}^{p(|x|)}}$[$M$ accepts $<x, t>$] $>$ 1/2.

• If $x\notin L$, then $Pr_{t∈\small\{0,1\small\}^{p(|x|)}}$[$M$ rejects $<x, t>$] $≥$ 1/2

Where $Pr_{t∈\{0,1\}^{p(|x|)}}$[$M$ accepts $<x, t>$] means the probability, for a give $t$ from the set $\{0,1\}^{P(|x|)}$, that M accepts the input $<x,t>$ is greater than 1/2. This is similar to the definition of bounded error probabilistic polynomial time(BPP), except that the definition for BPP have both equalities as $≥$, so I'm guessing I need to show that the language L is in BPP. But how would I even start the proof to show that he language is indeed in BPP. Also the definition of a language in BPP is not identical to what is mentioned in the question, so maybe there's a different approach to answering the question. Also, I don't need to explicitly find the polynomials $p$ and $T$, but instead argue that they exist.

Any help to assist me with the question would be much appreciated


1 Answer 1


Look again at your definitions. $\psi$ is a formula of $n$ variables, eg. $\psi_1 = x_1 \vee x_2$ or $\psi_2=x_1 \wedge x_2$, on 2 variables.

Now the question asks whether or not there are more than $2^{n-1}$ assignments to $x_1, x_2, ...$ that satisfy the formula. In other words, assignments that make $\psi$ evaluate to true. For the above example, $\psi_1$ has 3 satisfying assignments (out of the $2^2=4$ possible assignments), while $\psi_2$ is satisfied only by a single assignment (namely, $x_1=x_2=\text{true}$). So $\psi_1 \in L$ and $\psi_2 \notin L$.

If you understand so far, then finding a probabilistic TM that accepts any formula with the above conditions with probability at least $1/2$ is trivial. I'll let you think about it some more.

  • $\begingroup$ Thanks, I understand what $psi$ means now, but I'm struggling on how to prove that the machine $M$ exists. How would you in general show that a language $L$ is in a randomized complexity, such as RP(randomised polynomial time), coRP(complement randomised polynomial time), BPP(bounded error probabilistic polynomial time) and ZPP(zero error probabilistic polynomial time) $\endgroup$ Nov 25, 2014 at 17:39
  • $\begingroup$ Hint: pick a random assignment. What is the probability it will satisfy $\psi$ if $\psi \in L$? What is the probability it will satisfy $\psi$ if $\psi \notin L$? $\endgroup$
    – Ran G.
    Nov 25, 2014 at 23:38

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.