tag:blogger.com,1999:blog-3722233.post112610803619861928..comments2024-07-14T17:05:42.915-05:00Comments on Computational Complexity: P/polyLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-1126396085909179662005-09-10T18:48:00.000-05:002005-09-10T18:48:00.000-05:00the random access P/exp expressed above isn't very...the random access P/exp expressed above isn't very interesting - it contains every language.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126258997790366282005-09-09T04:43:00.000-05:002005-09-09T04:43:00.000-05:00It is worh noting that the "extra information in t...It is worh noting that the "extra information in the system" in the cryptographic application of P/poly has some unexpected consequences. For example, it is intuitive that zero-knowledge proofs should be closed under sequential composition...yet we only know how to prove it for P/poly adversaries (as far as I know). The use of P/poly adversaries (and simulators) also explains some of the work cryptographers must do in their definitions that may seem strange at first glance - you have to avoid things like adversaries that have keys "hard-wired" into them. <BR/><BR/>--David MolnarAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1126114836487857952005-09-07T12:40:00.000-05:002005-09-07T12:40:00.000-05:00Even this discussion seems a bit too narrow. The ...Even this discussion seems a bit too narrow. The real issue is the general issue of uniformity vs non-uniformity in computation and non-uniform computattion is of very substantial interest. <BR/><BR/>The second definition in terms of circuits is extremely natural. There are many other natural non-uniform classes such as non-uniform L defined by branching programs instead of circuits.<BR/><BR/>A better name for P/poly might be "non-uniform P" (maybe a notation P/) and we should reserve the awkward P/f(n) notation for cases when f(n) is a proper sub-class of polynomials. (Unless the advice string is random access, then P/exp would be the same class.)Anonymousnoreply@blogger.com