<p>Given a <span class="math-container">$\Sigma^p_2$</span>-complete oracle (i.e., <span class="math-container">$\Sigma_2 \mathrm{SAT}$</span>), I have a problem that requires to call this oracle polynomially many times and returns an integer. Essentially, this is a function problem (<a href="https://en.wikipedia.org/wiki/Function_problem" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Function_problem</a>.) I'm trying to prove the lower bound of this problem. Is there any canonical complete problem for <span class="math-container">$\mathrm{FP}^{\Sigma^p_2}$</span> that I can reduce from?</p>

CC BY-SA 4.0
2019-03-28T15:18:06.793Z
Hello and welcome to TCS.SE! Could you consider editing your question to add some background for readers unfamiliar with the class you are asking about, i.e., defining it from more common classes and adding a pointer to a place where it is defined more formally?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2019-03-28T16:48:50.660Z
I don’t know what’s canonical, but one complete problem for example is evaluation of circuits (with multiple output bits) using the standard Boolean gates and unbounded fan-in oracle gates computing, say, $\Sigma_2\mathrm{SAT}$.
Emil Jeřábek
CC BY-SA 4.0
2019-03-28T16:50:18.130Z
@a3nm This is a perfectly common notation. See https://en.wikipedia.org/wiki/Polynomial_hierarchy and https://en.wikipedia.org/wiki/FP_(complexity) (here it’s relativized).
Emil Jeřábek
CC BY-SA 4.0
2019-03-28T17:43:10.570Z
@EmilJerabek: I thought about $\Sigma_2 SAT$, but isn't that only complete for this class under Cook reductions? (should be complete for $\Sigma_2 P$ under Karp) unclear to me whether the question is about completeness under Cook or Karp reductions. The former is pretty trivial, as you say.
Joshua Grochow
CC BY-SA 4.0
2019-03-28T18:10:21.933Z
@JoshuaGrochow I was only referring to completeness under many-one reductions. $\Sigma_2\mathrm{SAT}$ is complete for $\Sigma^P_2$, while evaluation of circuits described in my comment is complete for $\mathrm{FP}^{\Sigma^P_2}$. In general, if $L$ is a complete language for a class $C$, then evaluation of multiple-output circuits allowing oracle gates for $L$ is $\mathrm{FP}^C$-complete.
Emil Jeřábek
CC BY-SA 4.0
2019-03-28T18:30:50.333Z
Ah, right, of course :)
Joshua Grochow
CC BY-SA 4.0
2019-03-29T00:45:31.953Z
@EmilJeřábek: This notation was not common to me at least. Thanks for the pointer.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2019-03-29T17:36:21.693Z
Thank you @EmilJeřábek for your comment. I think that is exactly what I am looking for. Do you have any more detailed reference about this?
mnajib
CC BY-SA 4.0
2019-04-01T15:42:57.250Z
Hi @a3nm, thanks for the warm welcome. I added some more background to the question, hope it's enough.
mnajib
<cc.complexity-theory><complexity-classes><polynomial-hierarchy>
Canonical complete problem for $\mathrm{FP}^{\Sigma^p_2}$
mnajib
# Canonical complete problem for $\mathrm{FP}^{\Sigma^p_2}$

(Asked by: username_0 on 2019-03-28)

Given a $\Sigma^p\_2$-complete oracle (i.e., $\Sigma\_2 \mathrm{SAT}$), I have a problem that requires to call this oracle polynomially many times and returns an integer. Essentially, this is a function problem (<https://en.wikipedia.org/wiki/Function_problem>.) I'm trying to prove the lower bound of this problem. Is there any canonical complete problem for $\mathrm{FP}^{\Sigma^p\_2}$ that I can reduce from?

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

> **Comments:**
> **username_1**: Hello and welcome to TCS.SE! Could you consider editing your question to add some background for readers unfamiliar with the class you are asking about, i.e., defining it from more common classes and adding a pointer to a place where it is defined more formally?  
> **username_2**: I don’t know what’s canonical, but one complete problem for example is evaluation of circuits (with multiple output bits) using the standard Boolean gates and unbounded fan-in oracle gates computing, say, $\Sigma_2\mathrm{SAT}$.  
> **username_2**: @a3nm This is a perfectly common notation. See https://en.wikipedia.org/wiki/Polynomial_hierarchy and https://en.wikipedia.org/wiki/FP_(complexity) (here it’s relativized).  
> **username_3**: @EmilJerabek: I thought about $\Sigma_2 SAT$, but isn't that only complete for this class under Cook reductions? (should be complete for $\Sigma_2 P$ under Karp) unclear to me whether the question is about completeness under Cook or Karp reductions. The former is pretty trivial, as you say.  
> **username_2**: @JoshuaGrochow I was only referring to completeness under many-one reductions. $\Sigma_2\mathrm{SAT}$ is complete for $\Sigma^P_2$, while evaluation of circuits described in my comment is complete for $\mathrm{FP}^{\Sigma^P_2}$. In general, if $L$ is a complete language for a class $C$, then evaluation of multiple-output circuits allowing oracle gates for $L$ is $\mathrm{FP}^C$-complete.  
> **username_3**: Ah, right, of course :)  
> **username_1**: @EmilJeřábek: This notation was not common to me at least. Thanks for the pointer.  
> **username_0**: Thank you @EmilJeřábek for your comment. I think that is exactly what I am looking for. Do you have any more detailed reference about this?  
> **username_0**: Hi @a3nm, thanks for the warm welcome. I added some more background to the question, hope it's enough.  

---

## 0 answers

