Talk:BPP
|
|
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 the fuck 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 fucking 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 stupidity 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 fucking 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.