Pergunta

I have some basic questions about complexity theory that came up when I tried to understand the result by Raz and Tal that BQP$^O\nsubseteq$ PH$^O$. Aaronsons paper was helpful, but I still have some questions left.

  1. Raz and Tal derive Corollary 1.5 from 1.4 "by the relation between black-box separations and oracle separations", but aren't those the same thing? I thought the following all mean the same:

    • black-box model
    • oracle model
    • relative/relativized problem
    • query complexity

    It would make more sense to me if Corollary 1.5 follows from 1.4 by the relation between promise problems and decision problems in the black-box model.

  2. I am not sure how to interpret the fact that there is randomness in the problem. I think of a class such as BPP as languages solvable by a regular Turing machine with access to a random tape, which can make an error with a constant probability over its random bits. However we need to consider the worst case instantiation of the problem (right?). For a language to be in PH, there needs to be a PH-machine (without access to randomness) that does not fail on any input. Now for any oracle-output coming from one distribution there is a non-zero probability that it was actually generated by the other distribution, so the PH-machine will be wrong sometimes. Why is that argument not sufficient to show that the problem is not in PH (or any other "zero-error" class for that matter)?

  3. What exactly is meant by an AC$^0$ circuit with access to an oracle? I've seen this described as "a circuit with access to the oracle's truth table", which I could understand if the oracle solved a decision problem $f: \{0,1\}^n \rightarrow \{0,1\}$, then the circuit input nodes are $x_i = f(i)$ for $i \leq 2^n$. However, here the oracle samples from one of two distributions on $\{\pm 1\}^{2N}$ and the circuit is defined as $A: \{\pm 1\}^{2N} \rightarrow \{\pm 1\}$. Does that mean the circuit only gets access to a single query output?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top