Complexity class of problems solvable using Q&A site - MathOverflow

Complexity class of problems solvable using Q&A site

2010-01-06T21:58:18Z

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

Answer by Mitch for Complexity class of problems solvable using Q&A site

2010-01-06T23:21:25Z

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.

Answer by Rune for Complexity class of problems solvable using Q&A site

2010-01-08T04:04:52Z

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.