tag:blogger.com,1999:blog-3722233.post85647197..comments2024-03-28T18:17:00.135-05:00Comments on Computational Complexity: Complexity Class of the Week: SPP, Part IILance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-82388501592892412232021-08-25T02:52:05.707-05:002021-08-25T02:52:05.707-05:00Sorry should it be properly x in L iff f(x) is 1 a...Sorry should it be properly x in L iff f(x) is 1 and not in L iff f(x) is 0?Anonymoushttps://www.blogger.com/profile/15215802322939426847noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19354075147763841522021-04-12T16:20:34.909-05:002021-04-12T16:20:34.909-05:00Thank you C=P seems analogous to NP though it is a...Thank you C=P seems analogous to NP though it is a counting class. But C=P is low for itself and #C=P seems to be #GapP while #NP is different compared to #P. If there was a Vazirani-Valiant perhaps it could be suspicious NP is low for itself and #P=#NP and UP=NP (perhaps there is a barrier to derandomizing because typically if we say derandomizing Valiant Vazirani we think of reduction to a *deterministic* set of instances at least one of which is a single witness instance).Anonymoushttps://www.blogger.com/profile/15215802322939426847noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84004733571650623352021-04-12T15:38:25.908-05:002021-04-12T15:38:25.908-05:00Valiant-Vazirani doesn't seem to work for Gap-...Valiant-Vazirani doesn't seem to work for Gap-P functions. The issues is that a Gap of zero might not stay zero when you eliminate a random set of witnesses.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41732450414354391002021-04-12T15:08:35.038-05:002021-04-12T15:08:35.038-05:00Thank you. I was also wondering following. EP is i...Thank you. I was also wondering following. EP is in C=P and the question of C=P is in RP^PromiseSPP which under derandomization would be C=P in P^PromiseSPP? The reasoning is if gap is 0 SPP can detect and if gap is $\neq0$ perhaps there is a gap version of Valiant-Vazirani (unlikely but has it been asked somewhere)?Anonymoushttps://www.blogger.com/profile/15215802322939426847noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88291233236718633012021-04-12T15:01:23.021-05:002021-04-12T15:01:23.021-05:00Yes and no. You can reduce GapP to a #P question b...Yes and no. You can reduce GapP to a #P question but asking whether the gap is one does not reduce to a UP question.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47077591712129304202021-04-12T14:58:49.940-05:002021-04-12T14:58:49.940-05:00I think GapP is in FP^#P and so is SPP in P^UP?I think GapP is in FP^#P and so is SPP in P^UP?Anonymoushttps://www.blogger.com/profile/15215802322939426847noreply@blogger.com