Let's say $F$ is an oracle for a problem in $\mathbb{NP}$, but I cannot call this oracle with any input instance. Instead, whenever I call $F$ I get returned a random instance and solution. Thus, I know that $F$ is in fact capable of solving arbitrary $\mathbb{NP}$-hard problems, I just can't specify which one I want it to solve.
Is it possible to use such an oracle to solve an $\mathbb{NP}$-complete problem faster? My gut says no because the naive use of the oracle still requires $O(2^n)$ time by calling the oracle enough to check every solution. I just can't think of a way to prove this.
Asked By : Mike Izbicki
Answered By : Tsuyoshi Ito
As Xodarap pointed out, if you require your algorithm with the "random oracle" to always output the correct answer, then the random oracle is useless. The problem becomes more interesting if we allow small probability of error (where the probability is with respect to the random instance chosen by the oracle).
In addition, as Vor pointed out in comments on the question, it is meaningless to say "random instance" without specifying a probability distribution. One of the reasonable assumptions to make here is that this random instance is chosen uniformly at random from the set of all strings of length p(n), where n is the input length and p is some fixed polynomial. We could make other, weaker, assumptions on the probability distribution.
Here we will make the assumption quite general, and will show that existence of a randomized polynomial-time algorithm with a "random oracle" for NP-complete problems has a surprising consequence even under this weak assumption.
Let's drop the requirement that the "random oracle" will solve a problem in NP (on a randomly chosen instance). Now the "random oracle" can be any predetermined probability distribution over polynomial-length strings, and every time it is asked, it emits a string according to this probability distribution. The only requirement is that this probability distribution depends only on the input length. Note that your model is indeed a special case of this model. In your model, the probability distribution is required to have the following form: it first chooses a uniformly random instance y from a set depending on the input length, and then returns a pair (y, g(y)), where g: {0, 1}*→{0, 1} is the characteristic function of some decision problem in NP. Now we allow any probability distribution, as long as the distribution is determined by the input length alone.
An "oracle" of this general form is called a randomized advice. The class of decision problems which can be decided by a randomized polynomial-time algorithm with a randomized advice (with bounded two-sided error) is called BPP/rpoly, and it is known that this class is equal to P/poly. (The inclusion BPP/rpoly⊆P/poly can be proved in the same way as a well-known inclusion BPP⊆P/poly. For a proof of the latter, see e.g. Theorem 6.3 of Goldreich [Gol08].)
This means that if an NP-complete problem can be solved in your model, then NP⊆P/poly. However, it is known that NP⊆P/poly implies that the polynomial hierarchy collapses to the second level [KW98, Cai07]. Most complexity theorists consider a collapse of the polynomial hierarchy as a big surprise. If we believe that the polynomial hierarchy does not collapse, then NP-complete problems cannot be solved efficiently with the "random oracle" in your sense.
References
[Cai07] Jin-Yi Cai. S2p ⊆ ZPPNP. Journal of Computer and System Sciences, 73(1):25–35, Feb. 2007. DOI: 10.1016/j.jcss.2003.07.015.
[Gol08] Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008.
[KW98] Johannes Köbler and Osamu Watanabe. New collapse consequences of NP having small circuits. SIAM Journal on Computing, 28(1):311–324, 1998. DOI: 10.1137/S0097539795296206.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/4717
0 comments:
Post a Comment
Let us know your responses and feedback