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.

  • $\begingroup$ 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. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.