Talk:PP (complexity)

A small comment on the following sentence: "This may be compared roughly to the problem of trying to figure out which side of a slightly-biased coin is more likely by flipping it many times."

Isn't this equally true for BPP and the Chernoff bound? Or rather isn't the bias of a coin independent of the size of any problem instance and thus constant? I am just afraid that this might be confusing to some readers.

--Anonymous 17:17, 30 April 2009 (UTC)

I think what the article is trying to say is that if your PP algorithm only outputs YES with probability 1/2+1/2ⁿ, then figuring out whether the actual answer is yes or no is like trying to decide the bias of a coin with a 1/2ⁿ bias, so it's going to take a long time and is not very useful. You're right, it may be confusing -- I've removed it for now. Regards, Shreevatsa (talk) 17:41, 30 April 2009 (UTC)

"PP compared to other complexity classes" argument

Is the argument of the section "PP compared to other complexity classes" actually correct? The given reduction seems to fail, as the probability of error for unsatisfiable instances is 1/2, but we require that the probability of error is less than 1/2 for all instances. The argument seems repairable, however. Here is the corrected reduction:

Given a SAT instance with $n$ variables, choose an assignment uniformly at random. If the assignment satisfies the SAT instance, output YES. If the assignment doesn't satisfy the SAT instance, output YES with probability ${\frac {1}{2}}-2^{-(n+1)}$.

This repairs the argument, because now the probability of error on unsatisfiable instances is less than 1/2, and with the observation that at least one in $2^{n}$ assignments satisfy any satisfiable instance, we see (with a little manipulation) that the probability of error on satisfiable instances is also less than 1/2.

I don't want to just change the prose without a citation on this argument, although my logic feels correct. Can someone either: a) either confirm the current prose as being obviously wrong and my argument as obviously correct (in which case I'll rewrite it), or b) tell me why the current prose is correct, or c) give a citation to a source that has a more complete discussion?

72.70.58.29 (talk) 07:12, 15 August 2017 (UTC)

I thought more about it, and consulted with a friend. I was being *extremely* silly, and forgot that PP allows the error to be 1/2 on no-instances. Please ignore me. 72.70.58.29 (talk) 12:32, 31 August 2017 (UTC)