In Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?, authors defined a new type of generic oracles named Kolmogorov generic oracles.

They proved following results relative to $G\oplus H$ where $G$ is Kolmogorov generic and $H$ is $PSPACE$-complete:

  1. $TFNP=FP$,
  2. $PH$ does not collapse,
  3. $P\not=UP$.

The following questions are about the Kolmogorov generic oracle $G$ and its definition:

Q1. The consistency of two conditions $p$ and $q$ means $p|_{D(p)\cap D(q)}= q|_{D(p)\cap D(q)}$ where $D(\alpha)$ means domain of $\alpha$. My question is about the meaning of consistency in the definition of an interval $U_p$. What is the meaning of the consistency of a condition $p$ with some subset of $U$ like $A$?

Q2. Theorem 5 says that relative to a Kolmogorov-generic oracle $G$, $P\not = UP$. In the proof of this theorem the language $L=\{\left<i,0^n\right>:\exists z(|z|=n \land\left<i,0^n\right>\in G\}$ is defined and it says that $L\not\in P^G$ without proof. What is the argument to prove $L\not\in P^G$?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.