Talk:Polynomial-time approximation scheme
I deleted the following statement from the article:
"An important class of problems which have an FPRAS, but were thought until recently not to have a PTAS, is the class of #P-complete counting problems.[1]"
I haven't read the reference, but it is definitely not true that all #P-complete problems have an FPRAS. This would, for instance, imply RP = NP. --Robin (talk) 13:24, 8 July 2009 (UTC)
- ^ Halman, Klabjan, Li, Orlin, Simchi-Levi, Fully polynomial time approximation schemes for stochastic dynamic programs, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, 700–709, 2008.