4
$\begingroup$

Is there a complexity class for problems such as the following?

Problem FindSum(s), where $s\in[0,1]$ is a real parameter:

Input: $g: [0,1]\to [0,1]$, a continuous monotone-increasing bijective function, specified by oracles that can answer queries of two kinds:

  • Given $x\in[0,1]$, what is $g(x)$?
  • Given $\alpha\in[0,1]$, what is $g^{-1}(\alpha)$?

Output: A point $x_0\in[0,1-s]$ for which $g(x_0) +g(x_0+s)=1$.

The problem definition is somewhat similar to definition of PPAD problems: in PPAD problems, too, the input is given by two complementary oracles ("previous node" and "next node"), and a solution is guaranteed to exist. However, the problem above considers arbitrary real numbers, as in the Real RAM model. Moreover, it can be proved that the problem cannot be solved by finitely many queries.

One can think of many similar problems. Is there a complexity class for them?

$\endgroup$
1
  • $\begingroup$ Maybe some languages defined by Büchi automata, depending on what you mean by "query". $\endgroup$ – Neal Young Apr 29 '19 at 14:41

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.