2
$\begingroup$

The definition of the class $UP$ is here. It is of course easy to see that $P\subseteq UP$.

I have a problem of proving that there is an oracle $O$ and a language $L$ such that $L\in UP^{\ O}$ but $L\notin P^{\ O}$, i.e. $UP^{\ O}\neq P^{\ O}$.

I find a lot of struggle of finding an explicit $O$, and more struggle to proof it without finding one. I don't have access to the paper which is in the complexity zoo in the link above, can you please explain why it is true or provide me with access to the paper?

$\endgroup$
  • $\begingroup$ The complexity zoo states that a random oracle would work. Have you tried working that out? $\endgroup$ – Yuval Filmus Jul 26 '17 at 6:58
1
$\begingroup$

Here is the construction from Rackoff's paper Relativized questions involving probabilistic automata. We construct the oracle $O$ using diagonalization, in steps. At step $t$ we will construct the initial segment $O_t$ of $O$ which consists of $O \cap \bigcup_{i=0}^{n_t} \Sigma^i$ for some $n_t$, where $n_0 < n_1 < \cdots$ is an increasing sequence. We will maintain the following invariant: $O_t$ contains at most one string of each length. This will guarantee that the following language is in $UP^O$: $$ L = \{ x : \exists y \in O \cap \Sigma^{|x|} \}. $$

The construction will use an enumeration $M_i$ of all polynomial time Turing machines, with the guarantee that the running time of $M_i$ is at most $in^i$. It is a standard fact that such an enumeration exists.

Let $O_{t-1}$ be the initial segment constructed at step $t-1$ (or $\emptyset$ in the first step). We now show how to construct $O_t$. Choose the smallest $a_t > n_{t-1}$ such that $ta_t^t < 2^{a_t}$. Run $M_t$ on the string $0^{a_t}$, answering NO to all queries outside of $O_{t-1}$. Let $b_t$ be the length of the largest string queried, and let $n_t = \max(a_t,b_t)$. If $M_t$ accepts, set $O_t = O_{t-1}$, guaranteeing that $0^{a_t} \notin L$. Otherwise, set $O_t = O_{t-1} \cup \{x\}$, where $x$ is some string of length $a_t$ which $M_t$ didn't query (such a string must exist since $ta_t^t < 2^{a_t}$), guaranteeing that $0^{a_t} \in L$. You can check that $O_t$ satisfies the invariant stated above.

By construction, $L \in UP^O$ (the UP machine guesses $y$ of the same length as the input and verifies that $y \in O$), while $L \notin P^O$ since $M_t$ answers incorrectly on the string $0^{a_t}$, by construction.

Beigel, in the paper On the relativized power of additional accepting paths, shows that $P^O \neq UP^O$ for a random oracle, crediting this result to Rudich's PhD thesis. In fact he proves even stronger separations, showing that allowing more accepting paths increases the (relativized) power of polytime machines.

$\endgroup$

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.