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

Consider the following game: Alice chooses a real function number $$x\in [0,1]$$; Bob has to guess the number by asking Alice any number of queries of the form "is $$x > a$$?" [where Bob can choose the $$a$$]. Obviously Bob cannot always win by asking a finite number of queries, since any finite number of such queries only reveals an interval of positive size in which $$x$$ can be found.

There are similar problems that cannot be solved by a finite number of queries, but the proof might be more complicated. For example, here, Stromquist has proved that it is impossible to find an envy-free cake-division using a finite number of "mark" and "eval" queries. This result can be stated as follows. Suppose Alice chooses three nonatomic measures $$v_1,v_2,v_3$$ on $$[0,1]$$. Bob has to find two numbers $$x,y\in [0,1]$$ such that, after possibly renumbering the measures, the following holds:

• $$v_1(0,x)\geq v_1(x,y)$$ and $$v_1(0,x)\geq v_1(y,1)$$ ;
• $$v_2(x,y)\geq v_1(0,x)$$ and $$v_2(x,y)\geq v_2(y,1)$$ ;
• $$v_3(y,1)\geq v_3(x,y)$$ and $$v_3(y,1)\geq v_3(0,x)$$ .

Bob cannot do this using a finite number of queries of the form "what is $$v_i(0,a)$$?" and "what is a $$b$$ such that $$v_i(0,b)=a$$?".

My question is: is there a known complexity class of problems that cannot be solved using a finite number of queries (for some precise definition of queries)? My goal is to prove that some other problems cannot be solved finitely, using a reduction from known problems in that class.

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