# A complexity-class of problems that cannot be solved in finite time

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?

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