2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Maybe some languages defined by Büchi automata, depending on what you mean by "query". $\endgroup$ – Neal Young Apr 29 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.