tag:blogger.com,1999:blog-3722233.post110560234577382977..comments2024-08-03T11:58:59.111-05:00Comments on Computational Complexity: Mandatory Technical Post (by guest blogger Rahul Santhanam)Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-3722233.post-1105647607596097062005-01-13T14:20:00.000-06:002005-01-13T14:20:00.000-06:00I use "FPRAS" for a randomized approximation schem...I use "FPRAS" for a randomized approximation scheme and "FPTAS" for a deterministic one. The question is whether for each FPRAS, one can find an equivalent FPTAS...<br /><br />As for the other question, one can define artificial #P-complete problems which have trivial FPTASs. Let f be a #P-complete function that is always bounded above by 2^{p(n)} for some polynomial p(n). Now define g = f + 2^{q(n)} for some larger polynomial q(n). g is #P-complete but the algorithm which just outputs 2^{q(n)} is an FPTAS for g (I'm not being completely precise but the argument can be made precise).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1105631064654078902005-01-13T09:44:00.000-06:002005-01-13T09:44:00.000-06:00I'm no expert in the area, but I thought the stand...I'm no expert in the area, but I thought the standard termonology was FPTAS, not FPRAS?<br /><br />Also, why do you restrict to "natural" problems in questions 1 and 2?Anonymousnoreply@blogger.com