tag:blogger.com,1999:blog-3722233.post6670392427379771547..comments2024-06-13T23:23:44.643-05:00Comments on Computational Complexity: Differentiation and IntegrationLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-18729407904999269232019-10-25T05:15:04.844-05:002019-10-25T05:15:04.844-05:00In calculus class, differentiation seems to be com...In calculus class, differentiation seems to be computationally easier than integration. To Jeff Cheeger, integration is "easier" than differentiation because the set of integrable functions strictly contains the set of differentiable functions. After all, there are functions for which integration is possible and differentiation is impossible (and not the other way around), so integration must be easier, right?<br /><br />In the same way, P is computationally easier than EXP, but EXP strictly contains P. There exist problems for which solution in exptime is possible but solution in polytime is impossible (and not the other way around), so solution in exptime is "easier."Dustin Mixonhttps://dustingmixon.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71783236210426524742019-10-24T18:47:06.707-05:002019-10-24T18:47:06.707-05:00Liouville solved this already. It's the basis ...Liouville solved this already. It's the basis of MACSYM and Maple and Mathematica ...<br /><br />https://en.wikipedia.org/wiki/Liouville%27s_theorem_(differential_algebra)<br /><br />It always surprises people that "strange functions" like <i>sqrt(tan(x))</i> actually have an anti-derivative in closed form.<br /><br />It also matters which field you're working over. In the complex domain, you need to make sure you're sitting on the "correct" Riemannian manifold.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50142775564006845202019-10-21T20:23:08.411-05:002019-10-21T20:23:08.411-05:00Well, symbolic differentiation is easier than symb...Well, symbolic differentiation is easier than symbolic integration.<br /><br />Anonymoushttps://www.blogger.com/profile/11067659793463483481noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17908459555807537272019-10-21T20:17:14.791-05:002019-10-21T20:17:14.791-05:00In a paper written by Ker-I Ko (survey I believe) ...In a paper written by Ker-I Ko (survey I believe) it is stated that computing the definite integral of a polynomial time computable real function is #P-hard so formally integrating is very hard even for computers isn't it? Rodolfo Condehttps://www.blogger.com/profile/05925108860448179537noreply@blogger.com