tag:blogger.com,1999:blog-3722233.post115254119269581768..comments2024-03-18T23:13:09.570-05:00Comments on Computational Complexity: Definitions of AdviceLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-1152598813950019052006-07-11T01:20:00.000-05:002006-07-11T01:20:00.000-05:00The promise classes do not have the problem with a...The promise classes do not have the problem with advice but they are different classes, sometimes much stronger than the original. For example promise-NP\cap co-NP, as Oded notes in his survey, is hard for NP, where NP\cap co-NP probably isn't.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152569990571180192006-07-10T17:19:00.000-05:002006-07-10T17:19:00.000-05:00The best reason for not using the "official" defin...The best reason for not using the "official" definition is that in general we'd like being solvable with poly-size circuits to be the same as being solvable with a polynomial amount of advice. Should a definition be standard just for historical reasons?<BR/><BR/>Of course, as Salil says, dealing exclusively with promise problems gets around all these issues in a very nice way.<BR/><BR/>Rahul.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152558813845732492006-07-10T14:13:00.000-05:002006-07-10T14:13:00.000-05:00The Karp-Lipton formulation actual gives the natur...The Karp-Lipton formulation actual gives the natural class (for NP intersect coNP, BPP, etc.) if you start with a class of *promise problems* (rather than a class of languages). Using classes of promise problems, quantifiers also behave nicely, e.g. it holds that MA=\exists BPP.<BR/><BR/>See Goldreich's survey "On Promise Problems" (Sec 7, June 05 version):<BR/>http://www.wisdom.weizmann.ac.il/~oded/prpr.htmlAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152548221857608222006-07-10T11:17:00.000-05:002006-07-10T11:17:00.000-05:00Actually, if you could provide a reference to a pa...Actually, if you could provide a reference to a paper that defines BPP/log in this more natural but less standard way, that would be great. After a bit of brainstorming, I propose calling it BPP/mlog, for "Merlinized advice". The difference between BPP/mlog and BPP/log is the same as the difference between MA and ∃BPP. In both cases, Merlin is an existentialist who only guarantees the boundedness condition when his message is good.Greg Kuperberghttps://www.blogger.com/profile/16655664043505766628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152544012239191642006-07-10T10:06:00.000-05:002006-07-10T10:06:00.000-05:00The Zoo defines BPP//log as BPP with randomness-de...The Zoo defines BPP//log as BPP with randomness-dependent advice, which is a different variation on the theme. Or at least, I don't see any equivalence.<BR/><BR/>You could perhaps convey what you want with parenthesization, i.e., by writing B(PP/log). This would be correct if PP and PP/log were interpreted as classes that produce a probability distribution on the set {accept,reject}.Greg Kuperberghttps://www.blogger.com/profile/16655664043505766628noreply@blogger.com