The theory of derandomization has had many successes, but challenges remain. Perhaps the most significant of these are finding a deterministic poly time (or even subexp time) algorithm for arithmetic circuit identity testing, and finding a deterministic NC algorithm for perfect matching. A question that hasn't received as much attention as the above is whether fully poly time randomized approximation schemes (FPRASs) for #P-complete problems can be derandomized.
Question 1: Is there a natural #P-complete problem which has a fully poly time deterministic approximation scheme?
A good candidate is counting satisfying assignments to DNF formula, for which the best deterministic algorithm is more than a decade old, and takes slightly super-poly time. There is a beautiful theory of Monte Carlo Markov Chain based FPRASs for #P-complete problems, but I don't believe it is known how to derandomize any of these FPRASs.
Now, to weaken Question 1 slightly... Say that a randomized approximation scheme A for a function f is an FPRAS with symmetry breaking if with high probability, A outputs a single value that's a good approximation to f (as opposed to garden-variety FPRASs, which may output different values on different sequences of random bits, subject to the condition that most of these values are good approximations to f). FPRASs with symmetry breaking were studied in a paper by Cai, Lipton, Longpre, Ogihara, Regan and Sivakumar.
Question 2: Is there a natural #P-complete problem which has an FPRAS with symmetry breaking?
Question 1 (and hence also Question 2) has a positive answer under Nisan-Wigderson style circuit lower bound assumptions, which imply that any FPRAS can be derandomized. Moreover, if any FPRAS can be derandomized, BPP = P. What about the weaker assumption that any FPRAS can be converted to an FPRAS with symmetry breaking?
Question 3: Does the assumption that every function f which has an FPRAS also has an FPRAS with symmetry breaking imply any collapse of conventional complexity classes?
I'm no expert in the area, but I thought the standard termonology was FPTAS, not FPRAS?
ReplyDeleteAlso, why do you restrict to "natural" problems in questions 1 and 2?
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...
ReplyDeleteAs 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).