Is there any relation between $\mathsf{PPP}\subseteq\mathsf{TFNP}$ and $\mathsf{UP}$? [closed]

Question

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?

Answer 1

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$. 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}$.