I'm struggling to understand a question I've been given. The question asks: Let A 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 A. 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 A exactly, is it an assignment such as A=(x_1 ∨ x_2 ∨ ... 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 A"?
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 ∈ L, then Pr_t∈({0,1})^p(|x|))[M accepts ] > 1/2.
• If x not in L, then Pr_t∈({0,1})^p(|x|))[M rejects ] ≥ 1/2
Where Pr_(t∈{0,1})^p(|x|) means the probability, for a give t from the set {0,1}^P(|x|), that M accepts the input 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