<p>I doubt any of these inclusions hold, though probably proving that is hard.</p>
<ul>
<li><p><span class="math-container">$\mathsf{UP} \subseteq \mathsf{P}^{\mathsf{PPP}}$</span>: this seems unlikely because PPP only captures one style of reasoning, whereas problems in UP can have unique witnesses for many different kinds of reasons. (It would be interesting to know if there are natural candidates witnessing this separation, even if the absence of natural candidates doesn't prove the containment.)</p>
</li>
<li><p><span class="math-container">$\mathsf{PPP} \subseteq \mathsf{FP}^{\mathsf{UP}}$</span>: This seems unlikely because there is no reason that either kind of output (a preimage of <span class="math-container">$0^n$</span> nor a collision) should be unique. Even though the proof that one of these two things must occur has one branch of the conditional being that <span class="math-container">$C$</span> is a bijection, that is not the only way for <span class="math-container">$0^n$</span> to be in the image.</p>
</li>
<li><p>For the other two, note that <span class="math-container">$\mathsf{TFNP}$</span> is sometimes said to correspond to <span class="math-container">$\mathsf{NP} \cap \mathsf{coNP}$</span>, though I think more accurately <a href="https://cstheory.stackexchange.com/a/37813/129">it is like <span class="math-container">$\mathsf{NPMV}_t$</span></a>. So it's sort of somewhere between <span class="math-container">$\mathsf{NP} \cap \mathsf{coNP}$</span> and <span class="math-container">$\mathsf{NP}$</span>, but either way, it being contained in <span class="math-container">$\mathsf{FP}^{\mathsf{UP}}$</span> would be surprising. (Though with randomized reductions it might be interesting to think about Valiant-Vazirani in this context.)</p>
</li>
<li><p>If you think of <span class="math-container">$\mathsf{TFNP}$</span> as like <span class="math-container">$\mathsf{NP} \cap \mathsf{coNP}$</span>, then <span class="math-container">$\mathsf{UP} \subseteq \mathsf{P}^{\mathsf{TFNP}}$</span> would be morally like <span class="math-container">$\mathsf{UP} \subseteq \mathsf{coNP}$</span>.</p>
</li>
</ul>

CC BY-SA 4.0
2021-02-04T16:53:07.877Z
2021-02-04T16:53:07.877Z
Joshua Grochow
<p>A complete problem for <span class="math-container">$\mathsf{PPP}$</span> is the pigeon problem which is 'Given a Boolean circuit <span class="math-container">${\displaystyle C}$</span> having the same number <span class="math-container">${\displaystyle n}$</span> of input bits as output bits, find either an input <span class="math-container">${\displaystyle x}$</span> that is mapped to the output <span class="math-container">${\displaystyle C(x)=0^{n}}$</span>, or two distinct inputs <span class="math-container">${\displaystyle x\neq y}$</span> that are mapped to the same output <span class="math-container">${\displaystyle C(x)=C(y)}$</span>'.</p>
<blockquote>
<ol>
<li><span class="math-container">$\mathsf{PPP}$</span> contains functional version of integer factorization, discrete logarithm etc. (page <span class="math-container">$148$</span> in <a href="https://simons.berkeley.edu/sites/default/files/docs/15391/ppp.pdf" rel="nofollow noreferrer">https://simons.berkeley.edu/sites/default/files/docs/15391/ppp.pdf</a> is reference). Decisional version of the problems are in <span class="math-container">$\mathsf{UP}$</span>. So is <span class="math-container">$\mathsf{PPP}\subseteq\mathsf{FP}^\mathsf{UP}$</span> or <span class="math-container">$\mathsf{UP}\subseteq\mathsf{P}^{\mathsf{PPP}}$</span> believed?</li>
</ol>
</blockquote>
<blockquote>
<ol start="2">
<li>Similarly is <span class="math-container">$\mathsf{TFNP}\subseteq\mathsf{FP}^\mathsf{UP}$</span> or <span class="math-container">$\mathsf{UP}\subseteq\mathsf{P}^{\mathsf{TFNP}}$</span> believed?</li>
</ol>
</blockquote>

<cc.complexity-theory><complexity-classes>
Is there any relation between $\mathsf{PPP}\subseteq\mathsf{TFNP}$ and $\mathsf{UP}$?
Turbo
# Is there any relation between $\mathsf{PPP}\subseteq\mathsf{TFNP}$ and $\mathsf{UP}$?

(Asked by: username_0 on 2021-02-02)

A complete problem for $\mathsf{PPP}$ is the pigeon problem which is 'Given a Boolean circuit ${\displaystyle C}$ having the same number ${\displaystyle n}$ of input bits as output bits, find either an input ${\displaystyle x}$ that is mapped to the output ${\displaystyle C(x)=0^{n}}$, or two distinct inputs ${\displaystyle x\neq y}$ that are mapped to the same output ${\displaystyle C(x)=C(y)}$'.

> 1. $\mathsf{PPP}$ contains functional version of integer factorization, discrete logarithm etc. (page $148$ in <https://simons.berkeley.edu/sites/default/files/docs/15391/ppp.pdf> is reference). Decisional version of the problems are in $\mathsf{UP}$. So is $\mathsf{PPP}\subseteq\mathsf{FP}^\mathsf{UP}$ or $\mathsf{UP}\subseteq\mathsf{P}^{\mathsf{PPP}}$ believed?

> 2. Similarly is $\mathsf{TFNP}\subseteq\mathsf{FP}^\mathsf{UP}$ or $\mathsf{UP}\subseteq\mathsf{P}^{\mathsf{TFNP}}$ believed?

**Tags:** cc.complexity-theory, complexity-classes

---

## 1 answers

### Answer by username_1 on 2021-02-04. Score: 2 | Accepted answer

I doubt any of these inclusions hold, though probably proving that is hard.

* $\mathsf{UP} \subseteq \mathsf{P}^{\mathsf{PPP}}$: this seems unlikely because PPP only captures one style of reasoning, whereas problems in UP can have unique witnesses for many different kinds of reasons. (It would be interesting to know if there are natural candidates witnessing this separation, even if the absence of natural candidates doesn't prove the containment.)
* $\mathsf{PPP} \subseteq \mathsf{FP}^{\mathsf{UP}}$: This seems unlikely because there is no reason that either kind of output (a preimage of $0^n$ nor a collision) should be unique. Even though the proof that one of these two things must occur has one branch of the conditional being that $C$ is a bijection, that is not the only way for $0^n$ to be in the image.
* For the other two, note that $\mathsf{TFNP}$ is sometimes said to correspond to $\mathsf{NP} \cap \mathsf{coNP}$, though I think more accurately [it is like $\mathsf{NPMV}\_t$](https://cstheory.stackexchange.com/a/37813/129). So it's sort of somewhere between $\mathsf{NP} \cap \mathsf{coNP}$ and $\mathsf{NP}$, but either way, it being contained in $\mathsf{FP}^{\mathsf{UP}}$ would be surprising. (Though with randomized reductions it might be interesting to think about Valiant-Vazirani in this context.)
* If you think of $\mathsf{TFNP}$ as like $\mathsf{NP} \cap \mathsf{coNP}$, then $\mathsf{UP} \subseteq \mathsf{P}^{\mathsf{TFNP}}$ would be morally like $\mathsf{UP} \subseteq \mathsf{coNP}$.


---

