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?

  • 1
    $\begingroup$ 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? $\endgroup$ – a3nm Mar 28 at 15:18
  • 2
    $\begingroup$ 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}$. $\endgroup$ – Emil Jeřábek Mar 28 at 16:48
  • 1
    $\begingroup$ @a3nm This is a perfectly common notation. See en.wikipedia.org/wiki/Polynomial_hierarchy and en.wikipedia.org/wiki/FP_(complexity) (here it’s relativized). $\endgroup$ – Emil Jeřábek Mar 28 at 16:50
  • $\begingroup$ @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. $\endgroup$ – Joshua Grochow Mar 28 at 17:43
  • 2
    $\begingroup$ @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. $\endgroup$ – Emil Jeřábek Mar 28 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.