# Show there exists a turing machine with the following properties

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

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.

• 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) – Andrew Brick Nov 25 '14 at 17:39
• 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$? – Ran G. Nov 25 '14 at 23:38