We will be trying to find what is the complexity class of problems solvable by a polynomial time algorithm (poster) that has access to a certain oracle (Q&A site) formalizing certain real-life concepts.


A question $Q$ is the number $N$ (polynomial in inputs of the problem) together with the polynomial time algorithm that returns yes/no for any input of size $\le N$.

An answer $A$ to question $Q$ is the string of size $\le N$ such that $Q(A)$ is true.

The Q&A site is an oracle which can be accessed by poster at any time and can be accessed multiple times; it immediately returns 0 or more strings which pretend to be an answer. Since it's easy to find whether a string is an answer, we can assume that the site returns only true answers (but it may return none).

Omniscient Q&A site

Consider the site AskAndReceive, which guarantees to return an answer if there is one (it's thus the ideal Q&A site). A poster using this site, I think, will be solving problems from the complexity class $P^{NP}$, that is $P$ using $NP$ as an oracle (correct me if I'm wrong).

Random Q&A site

Another Q&A site, BunchOfMonkeys, can only accept questions that look like $N$ zeroes and returns an answer that contains $N$ truly random bits. Is the complexity class solvable by the poster $BPP$?

Massively parallel Q&A site

Now let's try to construct interesting Q&A sites using only polynomial posters. For example, suppose that, given a question as above, the site is able to redirect this question to $2^N$ different instances of machines that run some given polynomial algorithm.

Let's be more specific: the machines run the algorithm that is property of site founders (and part of the definition of the site), so in particular they may decide to run whatever was given as part of the question. After the computation, the answers are collected in a parallel way, so that it only takes $N$ time to collect $2^N$ replies and return either an arbitrary answer, if found, or "no answers found".

What is the complexity class of problems solvable this way? How is it related to $P^{NP}$ and $BPP$?

  • 1
    $\begingroup$ +1. I love it! But you better watch out, since they say that Mathoverflow is not for questions about Mathoverflow... $\endgroup$ Jan 6 '10 at 22:32
  • 1
    $\begingroup$ Who said Math Overflow? I say oracles, parallel computations, proofs, randomness and monkeys with computers :) $\endgroup$ Jan 6 '10 at 22:39
  • $\begingroup$ It's a bit hard to understand what the model is in the third oracle. Can you clarify? Does the questioner get to specify the algorithm the $2^N$ machines run? If the answerers give back $2^N$ answers, wouldn't the polynomial-time questioner not even have time to look at all of them? $\endgroup$ Jan 7 '10 at 19:59
  • $\begingroup$ Re: clarification. Done so! $\endgroup$ Jan 7 '10 at 20:27

This question doesn't seem to be well-defined. First the poster is being restricted to ask only questions in FNP, i.e., questions whose answers can be verified in polynomial time. If this is the case, then the poster cannot obtain a truly random string from the monkeys, because the poster does not know how to check whether a given string is random or not.

Perhaps the real questions which you wish to ask are explained by the complexity classes that arise in interactive proof systems?

In short, if a probabilistic polynomial-time machine has access to an all-knowing Q&A site, then the polynomial-time question-poster can decide all languages in PSPACE with high probability. Similarly, If the poster has access to two such Q&A sites, then the poster can decide all of NEXP.


You're right about the first two oracles. In the first case this is, for instance, because polynomial-time Turing machines are equivalent to polynomial size circuits and Circuit-SAT is NP-complete. Hence, you're really just providing an oracle to an NP-complete problem. The second case is obvious.

Can you be more precise about the definition of the third example? The way it's phrased the oracle seems to be no more powerful than NP, since in NP you can check $2^N$ different instances simultaneously.

As another example, it might be interesting to allow some amount of parallelism, but limit the power of each machine more radically, e.g., AC$^0$ However, it seems that in any case you'll end up with something fairly standard in terms of complexity theory.

  • $\begingroup$ I updated the third oracle, and it seems to be NP indeed. $\endgroup$ Jan 7 '10 at 21:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.