8
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Perhaps you should modify the question in this way: "... whenever I call $F$ I get returned a random instance of size $n$ with uniform distribution ..." (where $n$ is the size of the input of the Turing machine that can access $F$). $\endgroup$ – Vor Sep 24 '12 at 22:33
  • $\begingroup$ @Vor, I thought about adding that stipulation as well, but I'm not sure it really makes a difference at all. Even if the distribution were such that it allowed a polynomial number of calls to get certain instances, it would still require more than polynomial calls to get a vast majority of instances. I think the only thing that matters is that the distribution is that I cannot somehow alter the distribution to skew it in favor of my specific instance. $\endgroup$ – Mike Izbicki Sep 24 '12 at 22:38
  • 1
    $\begingroup$ I agree with you, but without a bound/distribution "random instance" is meaningless. $\endgroup$ – Vor Sep 24 '12 at 23:02
  • 1
    $\begingroup$ I think by "faster" you mean "in P" but you might want to ask instead if it's in BPP. $\endgroup$ – Xodarap Sep 26 '12 at 13:13
  • $\begingroup$ @Xodarap I'm more interested in a method for using such an oracle to convert from any (hypothetically) more complex class into a weaker class. Not necessarily NP -> P. Also, I don't particularly see how probabilistic classes would be useful. $\endgroup$ – Mike Izbicki Sep 26 '12 at 15:55
8
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Let's specifically think about everyone's favorite NP-complete problem: 3SAT.

It's possible (albeit unlikely) that each time you call your oracle it gives you an assignment for the same instance. Specifically, each time it could give you an assignment for the trivial sentence:

$$(x\vee x \vee x)\wedge(x\vee x\vee x)\dots$$

But you already know the assignment for this. So your Oracle can't be useful.

More formally, if we call your oracle $A$, then $P^A\not=NP$ (assuming $P\not=NP$...)

$\endgroup$
  • $\begingroup$ It would not mean that any two 3SAT instances are polynomial time reducible. Only that they are polynomial time reducible given a random instance oracle. Right? $\endgroup$ – Mike Izbicki Sep 25 '12 at 19:53
  • $\begingroup$ Clarified; let me know if I'm not understanding what you mean by "random instance oracle". $\endgroup$ – Xodarap Sep 26 '12 at 13:10
  • $\begingroup$ Well, it will take an exponential number of calls to get an assignment for the same instance. In fact, it will take just as many calls as it would to get an assignment to the particular problem I'm trying to solve! You're throwing away all that work, and there may be some clever way to utilize it. $\endgroup$ – Mike Izbicki Sep 26 '12 at 15:58
  • $\begingroup$ @Mike: Complexity is concerned with the worst-case scenario. Since in the worst case the oracle is useless (as shown above), that's all we need to know. $\endgroup$ – Xodarap Sep 26 '12 at 16:40

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.