tag:blogger.com,1999:blog-3722233.post115099392427078096..comments2019-12-07T06:54:20.773-05:00Comments on Computational Complexity: Favorite Theorems: Probabilistic ComplexityLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-3722233.post-1151043341465372312006-06-23T02:15:00.000-04:002006-06-23T02:15:00.000-04:00Quantum computing seems to be rich in new algorith...Quantum computing seems to be rich in new algorithmic ideas, but it also seems somewhat 'orthogonal' to much of existing complexity theory, e.g. is difficult to relate to the polynomial hierarchy.<BR/><BR/>So, could QC inspire other models that don't share its physical plausibility but that have more use to classical complexity theory? This by way of analogy with PP, which isn't what one 'had in mind' for randomized algs but is nevertheless an upstanding complexity class.<BR/><BR/>As one example of what I'm thinking of, Scott Aaronson (quant-ph/0402095) shows you can solve NP-hard problems in BQP if you throw in some nonlinearity into QM. And there are others; I'm just wondering if this envelope could still be pushed.Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.com