# Diagonalization argument for MAJORITY

For any language $$A$$, define a language $$L_{A}$$ as:

$$L_{A} = \{0^{n}: \text{Number of strings in A of length n is more than 2^{n-1}} \}$$

I am trying to construct an $$A$$ such that $$L_{A} \notin P^{A}$$. It should intuitively be true, as a polynomial time machine cannot query an exponential number of strings and check whether a majority of them belongs to a language.

The proof boils down to a diagonalization argument. But I am unsure on how to construct the sets.

• These arguments typically have two parts: the query lower bound (which you mentioned) and the construction of the oracle. The first part follows by an adversary argument. If any path of the tree queried less than n/2 variables then it couldn't distinguish between a specific (based on the path) "Yes"-instance and a specific "No"-instance. The second part just applies the first part: each poly-time M_j on input 1^n induces a small decision tree (on the oracle) and so there's some oracle A_j for which M_j(1^n) fails to solve L(A_j) on inputs of length n. Then you basically "glue" these together. – Sam McGuire Jul 16 at 4:32

Let $$T_1,T_2,\ldots$$ be an enumeration of all timed polytime machines, machine $$T_i$$ running in time $$p_i(n)$$. We will construct $$A$$ in stages. At each stage, the truth value of $$A$$ is defined on only finitely many inputs.
Stage $$i$$ handles $$T_i$$. Choose an input length $$n$$ such that (i) $$A$$ is completely undefined and (ii) $$p_i(n) < 2^{n-1}$$. Run $$T_i$$ on $$0^n$$. Each time $$T_i$$ queries some yet undefined string in $$A$$, answer arbitrarily and fix the value of this string in $$A$$. Since $$p_i(n) < 2^{n-1}$$, in particular $$T_i$$ queries fewer than $$2^{n-1}$$ strings of length $$n$$. If $$T_i$$ answered "Yes", then define all remaining strings of length $$n$$ to be outside $$A$$. If $$T_i$$ answered "No", then define all remaining strings of length $$n$$ to be inside $$A$$. Either way, the machine $$T_i$$ is wrong on input $$0^n$$.
After infinitely many steps, we have defined $$A$$ at infinitely many strings, but probably not all strings. Define $$A$$ arbitrarily on all remaining strings.
We note that the same proof works for every (time constructible) complexity class in which a machine cannot make at least $$2^{n-1}$$ queries on input of length $$n$$.