### Motivation

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.

### Definitions

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$?

aboutMathoverflow... $\endgroup$ – Joel David Hamkins Jan 6 '10 at 22:32