Talk:BPP (complexity)

Untitled

Some examples of BPP / BPP-complete problems might be appreciated

What does this 1/4-clause mean in long run ? That chance of failure in many runs is (1/4)^N, 1/2*(1/2)^N or what ? --Taw

The idea is that running it n times and choosing the answer that occurred most often (a "majority vote") will almost always be correct for relative small n (like say, 20-50). The calculations aren't quite as simple as you describe, but are a consequence of the Chernoff bound. Deco 10:31, 24 Mar 2005 (UTC)

---

I'm not familiar with Wikipedia customs, and English is not my mother tongue, so I may not express myself clearly enough, but let me ask a question to all the editors of this page: Those who don't understand computational complexity theory why don't just shut up here? I quote: "The existence of certain strong Pseudorandom number generators imply that P=RP=BPP. This implication is conjectured to be true."

Jesus. The implication is true, it is not a conjecture, it is a theorem by Nisan and Wigderson. The existence of those generators is the conjecture, which depends on certain hardness assumptions. There are several such results, I think the latest and strongest is by Impagliazzo and Wigderson from 1997, who prove that P=BPP if E contains a language which has 2^Omega(n) circuit complexity for almost every n.

This even got a corrected version: "It has been conjectured that the existence of certain strong pseudorandom number generators implies that P=RP=BPP." Just as stupid as the previous one.

Let me politely ask everyone here not to edit this page if he/she doesn't have a clue about the subject.

Please, no personal attacks. Your change is correct to my knowledge, and we appreciate the help. The original editor's knowledge may have been out-of-date, since this is not a classical result, or it may have been referring to some stronger result based on a stronger definition. I'm not really sure what happened, but even experts make incorrect statements in their area. Deco 04:47, 4 Jan 2005 (UTC)

The above commenter may know one thing about complexity theory, but does not know anything about manners. He/she definitely does not represent the complexity theory community, which I know to mostly contain very nice and respectful people. --Boaz, March 21, 2005.

---

Hmm. There is some subtle difference between P and BPP. Example: Let we have probabilistic algorithm for adding two binary numbers of length n. This algorithm uses rnd() somewhere. On non-deterministic turing machine, this algorithm will have probability of success A , that can be made close to 1 by computing it many times (it is never 1 , but with some luck i can expect to get correct results).

On deterministic turing machine, one has to use pseudorandom number generator always seeded with same value(otherwise algorithm isn't deterministic), and this algorithm will fail for some inputs. Thus it is not an universal algorithm for adding binary numbers. The difference is subtle, but it is there. It has nothing to do with complexities, it's purely linguistical; it's just that P algorithm for addition of binary numbers does solve one problem (for pair of binary numbers, compute sum), and "BPP" algorithm using pseudorandom numbers solves other problems (for SOME pairs of binary numbers, give out sum, for some pairs, give out garbage)

So: If there is no algorithm that solves certain problem A in polynomial time, there could quite well be BPP algorithm for doing same thing _sometimes_(sometimes it will solve and sometimes it will fail)in polynomial time. And using strong pseudorandom number generator, there will be deterministic polynomial time algorithm for solving this problem for some inputs. But generally speaking, this algorithm will not be the solution to original problem A, because it will only work for some inputs.

My point is that "there is P algorithm to some problem A" and "there is BPP algorithm for some problem A" mean different things and you can not use pseudorandom number generator to turn latter into former (you will get "P algorithm that solves A for some restricted set of inputs and gives out garbage for other set")

--DL , December 03, 2005.

You are correct that ordinary pseudorandom number generators cannot (as far as we know) be used to produce polynomial-time algorithms based on BPP algorithms; instead, a source of "true" randomness is required. It has been proven that some probabilistic algorithms can solve a problem in polynomial time given only a small number of random bits, just enough for a "seed". It is an open question in research whether P=BPP, and research in this direction has generally followed the idea of producing pseudorandom generators sophisticated enough to actually replace truly random bits in certain applications. But to claim as a matter of fact that P≠BPP is really jumping the gun - there's convincing evidence to the contrary. Deco 19:29, 3 December 2005 (UTC)

I think you have not read what I wrote well enough. Issue has nothing to do with strength of pseudorandom numbers(longer explanation on bottom of page). Yes, with strong pseudorandom numbers you can emulate non-deterministic machine, and for sake of this talk i can assume that you emulate it perfectly. But it only let you turns what we name "BPP solutuion to problem A" into what is named "P solution for problem A that gives out garbage for certain inputs", and latter is NOT equivalent to "P solution for problem A [it is implied that it'll work for all inputs]". It's classic example of English terminology being not accurate enough to clearly specify the difference between "being able to emulate BPP on deterministic machine", and "BPP solution to problem A" being equivalent to "P solution to problem A". I agree with you that with strong pseudorandom number generator you can run BPP algorithms on deterministic machine. But it is not related to what i argue about.

P=NP or P=BPP?

Is it really true that one of P=NP or P=BPP is true? I find this a bit hard to believe. Who added this claim (regarding exponential size circuits for EXPTIME) and where's your reference? Thanks. Deco 19:37, 3 December 2005 (UTC)

I've commented out that paragraph, since it's most likley wrong. P=NP would imply P=BPP, so the disjunction (P=NP or P=BPP) would in turn imply P=BPP unconditionally. This is not known to be the case. --MarkSweep (call me collect) 18:18, 4 December 2005 (UTC)

BPP and P terminology/linguistics

My point is that:

Let I have developed "BPP algorithm for adding two binary numbers", and "P algorithm for adding two binary numbers" (i.e. both algorithms works in polynomial time but former fails with probability 1/3). Them are in fact solving two different problems:

"BPP algorithm" solves the problem SOMETIMES, and "P algorithm" solves it ALWAYS.

On deterministic machine, result depends soliely to input. If you "convert" BPP to P using pseudorandom number generator, no matter how strong, you will get "P algorithm that gives out sum for SOME pairs of binary numbers (and for some it gives garbage)". (unless you believe that with your pseudorandom number genrator it will work way better than it worked with true random numbers :-) )

So, there is "P algorithm that gives sum for ANY pair of binary numbers", and "P algorithm that gives sum for SOME pairs of binary numbers (and garbage for other pairs)".

It is clear that these two algorithms are solving _different_ problems. It has precisely nothing to do with strength of pseudorandom number generator, as long as it is deterministic.

You could even use "ultimately strong" (pseudo?)random number source, such as file with data obtained from true random number generator. (we can say that this file is part of algorithm :-) It's as close to true randomness as you can get on deterministic machine (even to the point that some people would argue it isn't deterministic :-) ). But the _only_ property i use is that with same seed it gives same sequence, so my argumentation will work regardless of strength of random number generator, or even with true random numbers if them is written to file for repeatability.

If you are thinking about using different seeds and "inheriting" seed from previous run like how you do that in software, then you get "P algorithm that takes seed and pair of binary numbers, and for some parameters gives out sum of binary numbers (for other, garbage), and the final random seed" (It's not original problem at all.)

In summary, my point is: If we say that "there is BPP solution to problem A" it doesn't imply that we can say "there is P solution to problem A". However, with strong pseudorandom numbers, we can run same BPP algorithm on deterministic machine and get P solution to problem A that gives correct result for SOME inputs, and garbage for other. But it's not what we can name "P solution to problem A" because this BPP-like solution would give garbage for other inputs. If number of possible inputs is infinite, no matter from how many trials you compute majority vote, there will be some inputs when this algorithm will give out garbage.

Anyway, it absolutely doesn't matter what I think on subject and what logical reasoning i do have. If there is no references to research where it is shown that "existence of strong pseudorandom number generaturs implies BPP=P", or that "NP=P or BPP=P", these claims is "original insight", and it's way worse than "original research". Or maybe these claims is really trivial(i don't think it is the case), then whoever inserted them must provide proof. Sure, if it's so trivial that it doesn't need reference he shouldn't have problems proving it in few lines.

My point is related to terminology and linguistics. The problem is that when we say that "problem is BPP" and when we say "problem is P" it has different meanings regardless of random number generators. It is related to the human language. I actually agree that (most likely) problems that are in BPP are in "P that is allowed to fail for some inputs".

--DL , December 04, 2005. (will register soon.)

I'm not sure I begin to understand your objection, but this won't stop me from trying to say something: Don't confuse problems with algorithms. Take a problem such as SATISFIABILITY: it asks whether a given propositional formula has a satisfying truth assignment. Now we can build several algorithms which work on this problem. Some of them will always return the correct answer while potentially taking a very long time. Some of them will return the correct answer most of the time while never requiring an unreasonable amount of time. Some of them will almost never return the correct answer, but will be blazingly fast.

The class BPP is a class of problems. It consists of those problems for which algorithms exist which, loosely speaking, produce the correct solution more often than not, and in reasonable time. So a direct way of showing that a given problem is in BPP is to exhibit a polynomial-time algorithm with a better-than-average chance of obtaining the correct answer.

As discussed above, a key issue is to quantify the computational advantage provided by a truly random source over a deterministically generated pseudorandom sequence. One way of proving P=BPP would be to show that there exist strong pseudorandom number generators that cannot be distinguished from a truly random source by an algorithm that is constrained to run in a certain amount of time. --MarkSweep (call me collect) 18:36, 4 December 2005 (UTC)

Okay, say we define a class ErrorP of problems such that some instances can be solved correctly in polynomial time, while other instances are solved incorrectly. In this case, your argument does clearly verify that BPP is contained in ErrorP. Unfortunately, this isn't very useful, because just about every problem is in ErrorP (just hard code the answer to one instance and return no for the rest). You can try to specify that it's only rarely wrong, but if you choose an arbitrary random number generator, it may so happen that you choose one that happens to get many instances wrong, perhaps almost all instances.

Related is the idea of universal hashing, which says that, with high probability, any hash function from a class of functions is unlikely to produce long chains on random inputs. If one doesn't work, we can change to another and hope it works. Simple linear congruential random number generators are an example of such a class. But I don't know of any way to ensure that you will get a hash function that won't produce long chains or to show that this is unlikely if you choose a generator at random. Deco 19:25, 4 December 2005 (UTC)

The trick to showing that P = BPP is that, while any one seed may fail for certain inputs, a "good" random number generator will work for any input, given the correct seed. Then it's just a matter of looping over all possible seeds, which can be done in polynomial time, provided the required seed size is at most logarithmic in the problem size. Ben Standeven 00:43, 24 March 2006 (UTC)

That would only work for P = RP. To show P = BPP, you need to be able to decide that a particular seed was one of the correct seeds.

JumpDiscont (talk) 20:15, 13 July 2010 (UTC)

Most seeds are correct. You are supposed to loop over all possible seeds, and (for BPP) take a majority vote among the answers received.—Emil J. 11:42, 14 July 2010 (UTC)

Is your idea that it _should_ be easy to show that most seeds are correct, or that someone has already shown that for some specific (hopefully nonempty) class of prngs, most seeds are correct?

JumpDiscont (talk) 20:20, 14 July 2010 (UTC)

It's not my idea, it's the definition of a pseudorandom generator. See e.g. the classical Nisan–Wigderson paper[1].—Emil J. 10:08, 15 July 2010 (UTC)

BPP and Monte Carlo

Is BPP equivalent to Monte Carlo? We have elsewhere ZPP is equivalent to Las Vegas. -Ozga 20:18, 27 March 2006 (UTC)

Yes, BPP-algorithms are equivalent to one of those casino towns. -- EJ 22:39, 27 March 2006 (UTC)

Would it be a good thing to mention this in the article? I think so. -- Ozga 05:36, 28 March 2006 (UTC)

Papdimitriou defines Monte Carlo as equivalent to RP. Hmm. Ozga 17:06, 30 March 2006 (UTC)

BPP is referred to as "Atlantic City," not Monte Carlo or Las Vegas. Sadeq 04:44, 17 August 2007 (UTC)

Bounds

The bound e^−k/18 on the error for k runs is suboptimal, it seems to be an artifact of whatever general version of Chernoff's bound was used to derive it. The actual value is of the order ${\frac {1}{\sqrt {k}}}\left({\frac {2{\sqrt {2}}}{3}}\right)^{k}$, which is about $e^{-k/16.98}\,$. It does not make any practical difference (especially since the convention of using 1/3 for the error of one run is itself completely arbitrary), but still I think that it is a bit misleading to give arbitrary numbers in the table which make a false impression of being tight. — Emil J. 19:07, 11 November 2009 (UTC)

I agree. What do you suggest? Putting in the value "16.98" also seems pretty pointless. --Robin (talk) 22:00, 11 November 2009 (UTC)

I'm not quite sure what would be the best way to solve it. Maybe just say something like "2^−ck for some constant c > 0", and leave the exact value unspecified? — Emil J. 11:44, 12 November 2009 (UTC)

The phrase "for some constant c > 0" seems too long to put in the infobox. But I have no other ideas, so go ahead with this. Maybe someone will think of something better. --Robin (talk) 13:01, 12 November 2009 (UTC)

OK, I've implemented the change. Feel free to fix it if you get a better idea. — Emil J. 13:20, 12 November 2009 (UTC)

k runs

In the table next to the intro/definition, I believe the 2^{-ck} error bounds for k runs are incorrect, because majority voting doesn't converge that fast. This should be 2^{-c*sqrt(k)} I believe. 62.166.189.223 (talk) 10:33, 25 January 2023 (UTC)

See the above section. I think the table is correct and this is the result you get from Chernoff bounds or "probability amplification" or "majority voting" or whatever you want to call it. I did a search and saw a few different lecture notes that I think give equivalent results to $2^{-ck}$ e.g. $e^{-k/18}$, depending on the precise Chernoff bound. — Bilorv (talk) 13:41, 28 January 2023 (UTC)