Talk:P/poly

Example

I'm trying to think of a good example of a P/poly algorithm to add to this page, but I can't think of anything nontrivial and interesting. Trivial examples include: problems in P and arbitrary unary languages. The NP in P/poly implies PH collapse result implies that there's no known P/poly algorithm for any NP-complete problem. The BPP in P/poly result implies that there is a relatively simple P/poly algorithm for primality testing, but is it simple enough to present here? The only other problems that might have one are integer factorization and graph isomorphism, but I know no result regarding whether either of these problems is in P/poly. Dcoetzee 21:40, 8 July 2007 (UTC)

Follow-up thought: it might be illustrative to show a P/poly algorithm for a problem in P if that algorithm is fundamentally different from the ordinary P algorithm, perhaps simpler, and uses the advice string in an interesting way. Dcoetzee 21:47, 8 July 2007 (UTC)

An obvious example would be to find a prime greater than a given number. 193.144.198.250 (talk) 08:36, 17 March 2014 (UTC)

Bug in the proof of Adleman's theorem

I think the proof is incorrect: Repeating M t times does NOT decrease the error probability below $1/3^{t}$ but it does decrease it to $<e^{-t/18}$ (by Chernoff bound, see BPP (complexity)). If we take $t=18n$, we get the probability of bad R for every x less than $(2/e)^{n}<1$. Kukolar (talk) 08:01, 10 May 2009 (UTC)

You're quite right. Fixed now. — Emil J. 16:05, 23 June 2009 (UTC)