0
$\begingroup$

If we let a language L in {0,1}* be dyadic if for each x in L, and each index i with xi = 1, i is a power of 2, then consider the class of languages recognized by a polynomial time oracle machine with a dyadic oracle. Is this the same as the class P/poly? If we start with some language L in P/poly, then we can use the advice string and the input x to generate a dyadic language, and then check various strings for each input x on the oracle to see if they are in our language to determine if x is in L. Is this the right idea? I also don't know how to approach the other direction. Do you need to create a circuit based on the queries to the oracle?

$\endgroup$
1
  • $\begingroup$ What do you mean by "use the advice string and the input x to generate a dyadic language"? $\endgroup$
    – Johnny
    May 8, 2023 at 0:22

1 Answer 1

0
$\begingroup$

Let $D \subseteq \{0,1\}^*$ be the class of all dyadic languages. Then by $P^D$, we denote the class of languages decidable in polynomial time by a Turing machine with an oracle for a Dyadic language.

Given a dyadic string $x \in \{0,1\}^m$, denote by $B(x)$ the string $y$ such that $y_i = x_{2^i}$. Intuitively, you can think of $B(x)$ as "compressing" $x$ by removing all the $0$ indices in between the indices which are powers of $2$. Now given a dyadic language $L$, let $B(L) := \{B(x) : x \in L\}$.

Claim: $D \subseteq P_{\text{poly}}$

Proof Let $L \in D$, and we describe a polynomial size circuit family $\{C_n\}$ which computes $L$. Let $L_n := \{x \in L : |x| = n\}$. Note that $B(L_n) \subseteq \{0,1\}^{\log n}$, so the naive DNF circuit which computes it has size $\log n \cdot 2^{\log n} = n \log n$. Our circuit $C_n$ simply wires $x_i$ for which $i$ is a power of $2$ into the $i$th input for this naive DNF circuit for $B(L_n)$.

It then follows that $P^D \subseteq P_{\text{poly}}$.

$\endgroup$
1
  • 1
    $\begingroup$ Oh okay that's very helpful thank you! I was having trouble constructing something that functions as B(L) is your solution so this made it very clear $\endgroup$
    – dino-t
    May 16, 2023 at 22:17

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.