show/hide this revision's text 4 fix

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 then collect 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 anyfound, or "no answers found".

What is the complexity class of problems solvable this way? How is it related to $P^{NP}$ and $BPP$?
show/hide this revision's text 3 edited tags
show/hide this revision's text 2 fixes

Complexity class of problems sovable solvable using Q&A site

Motivation

In short, we

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).

This is the most reasonable formalization of real-life concepts of this document I could come up with, but feel free to correct me!

Omniscient Q&A site

Consider an example the site AskAndReceive, which guarantees to return an answer if there is one (it's thus the ideal Q&A site). A poster together with with 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$?

Distributed

Massively parallel Q&A site

Here's a different model for

Now let's try to construct interesting Q&A sites : suppose you're getting an answer from a very large number of using only polynomial posters. One then tries to find out what should be the properties of the site so that it can approximate the ideal Q&A site. For example, suppose that, given a question as above, the site is able to implement a given distributed algorithm that requires less then $N$ bits of salt by giving a problem redirect this question to $2^N$ different peopleinstances of machines that run some given polynomial algorithm (property of site founders) and then collect answers, if any.

What is the complexity class of problems solvable this way? How is it related to $P^{NP}$ and $BPP$?
show/hide this revision's text 1