Why is differentiating mechanics and integration art? It is often said that "Differentiation is mechanics, integration is art." We have more or less simple rules in one direction but not in the other (e.g. product rule/simple <-> integration by parts/u-substitution/often tricky).
There are all kinds of anecdotes alluding to this fact (see e.g. this nice one from Feynman). Another consequence of this is that differentiation is well automatable within CAS but integration is often not.
My question
We know that there is a deep symmetry based on the Fundamental theorem of calculus, yet there seems to be another fundamental structural asymmetry. What is going on here...and why?
Thank you
EDIT
Some peope asked for clarification, so I try to give it. The main objection to the question is that asymmetry between two inverse operations is more the rule than the exception in math so they are not very surprised by this behaviour.
There is no doubt about that - but, and that is a big but, there is always a good reason for that kind of behaviour! E.g. multiplying prime numbers is obviously easier than factoring the result since you have to test for the factors doing the latter. Here it is understandable how you define the original operation and its inverse.
With symbolic differentiation and integration the case doesn't seem to be that clear cut - this is why there are so many good discussions taking place in this thread (which by the way please me very much). It is this Why at the bottom of things I am trying to understand.
Thank you all again!
 A: Differentiation is inherently a (micro-)local operation.  Integration is inherently a global one.
EDIT: the reason that locality helps with symbolic differentiation of elementary functions (and is not present to help with symbolic integration of the same functions) is that the basic arithmetic operations used to build elementary functions are simpler locally than they are globally.  In particular, multiplication and division become linear in the infinitesimal variables,
$$ (f + df) (g + dg) \approx fg + f dg + g df$$
$$ \frac{f+df}{g+dg} \approx \frac{f}{g} + \frac{g df - f dg}{g^2},$$
leading of course to the product and quotient rules which are two of the primary reasons why symbolic differentiation is so computable.  
Note that properties such as holomorphicity, mentioned in the comments, are not quite as local as differentiation, because in order to be holomorphic at a point, one must not only be complex differentiable at a point, but also complex differentiable on a neighbourhood around that point.  (In the jargon of microlocal analysis, it is merely a local property rather than a microlocal one.)
Finally, the reason why the inverse of a local operation (differentiation) is global is because differentiation is not locally injective (constants have zero derivative).  In order to eliminate this lack of injectivity, one needs to impose a global condition, such as a vanishing at one endpoint of the domain.
SECOND EDIT: Another way to see the relationship between locality and computational difficulty is to adopt a computational complexity perspective.  A Newton quotient, being local, only requires O(1) operations to compute.  On the other hand, a Riemann sum, being global, requires O(N) operations to compute, where N is the size of the partition.  This helps explain why the former operation preserves the class of elementary (or bounded complexity) functions, while the latter does not.  
(This is only if one works in the category of exact calculation.  If one is instead interested in numerical calculation and is willing to tolerate small errors, then the situation becomes reversed: numerical integration, being more stable than numerical differentiation, usually has lower complexity thanks to tools such as quadrature.  Here, one can turn the global nature of integration to one's advantage, by allowing one to largely ignore small-scale structure, assuming of course that the integrand enjoys some regularity.)
A: Both derivatives and integrals are limits. Now consider what they are limits of. Clearly, a difference quotient is a simpler expression than a sum of a bazillion terms.
A: This is a collection of a few ideas. Let me see where it takes us. 
It is probably too verbose since I am writing it as I think the question.
Maybe later I can shorten it and correct errors.
If you are hurried it is safe to scroll down to the last part, where there is 
what I think is an answer to the OP's question.

I want to concentrate on differentiation and integration as symbolic operations.
For differentiation we can consider a class $E$ of functions-symbols that contains the constants (complex constants maybe), $x$, is closed under the arithmetic operations, and composition. We can throw in other function-symbols like $e^x$, $\ln(x)$ together with $x^{-1}$, or many others. But notice that for every new function-symbol we throw in $E$ we assume we know how to compute its derivative (we have a symbol for it). The minimal assumption of having the constants and $x$ gives us $E$ to be the polynomials. A larger option would be the elementary functions. 
If differentiation is considered as an operation in the symbols in $E$ then it is, by the definition of $E$, an algorithmic operation. Given a function-symbol from $E$ (which by this act it is assumed to be formed from a few symbols for which we know the derivative and arithmetic and composition operations) we can compute its derivatives because the properties of differentiation cover the operations generating $E$. In principle, what might be hard is the question of whether a function belongs to $E$.
Claim: Integration is, at least, as hard as derivation. (maybe harder)
This is clear for the case of polynomials, which are always contained
in a reasonable minimal E.

Observation: The tentative claim that integration is harder than derivation is going to necessarily depend on $E$, since for $E$ being the polynomials both are simple operations. 
_

Let us consider now constructing a domain, as we have have done for differentiation, that is adapted to the operation of integration. Consider $I$ to be a collection of function-symbols, that contains the constants, $x$, and possibly others $e^x$, $x^{-1}$, ... for which we assume we know their integrals. Assume that $I$ is closed by the following operations:
If $f$ and $g$ are in $I$,


*

*$af+bg\in I$ for any constants $a$ and $b$. And the operations:

*$f\oplus g:=fg'+f'g\in I$

*$f\otimes g:= (f\circ g)\cdot g'\in I$


An $I$ like this is a reasonable minimum domain in which to define integration. It is clear that in such an $I$, integration is algorithmic, for a given function written using these operations. 
Claim: In $I$, derivation is simple if we assume $I$ contains the constants and either 2 or 3 are satisfied.
In fact, for a given f in I, its derivative is f'=f⊕1=1⊗f$.

This means that just one basic operation in $I$ allows to compute derivatives.
_

To translate the OP's question into another question:
Given an $E$ we already have a way to define linear combinations with constants, $\oplus$ and $\otimes$, since these are defined using the operations allowed in $E$. So, for an $E$ to be an $I$ or to form out of it a $\subset I$ we would need to have an algorithm that checks whether an element of $E$ is an $I$ (can be written using function-symbols with function-symbols integrals, linear combinations with constants coefficients, $\oplus$, and $\otimes$).
We have that the existence of such an algorithm depends on the $E$, on the function-symbols available in it. For $E$ being the polynomials in $x$ it is clear we have such an algorithm and it is simple. 
We have also that for some $E$ the problem is undecidable. From Richardson's theorem we know that if $E$:


*

*Contains $\ln(2),\pi,e^x,\sin(x)$

*Contains $|x|$ and

*Contains a function with no primitive in $E$ 


Condition $3$ is satisfied for the $E$-closure of the elementary functions together with $|x|$, since we can take $e^{x^2}$ to verify $3$.
The theorem is true because they manage to prove there is an elementary function (using also $|x|$) $M(n,x)$ which is identically to either $0$ or $1$ for each natural number $n$ but for which it is undecidable for every natural number $n$ whether it is identically $0$ or $1$. Given such a function then, if we could decide integration in $E$, then we could decide, for each natural number $n$, whether $f_n(x):=e^{x^2}M(n,x)$ is integrable or not. But this would tell us when $M(n,x)$ is zero or one, since $f_n(x)$ is integrable when $M(n,x)=0$ and non-integrable in $E$ when $M(n,x)=1$.
So, for certain classes $E$ we have that, while derivation is elementary (after having shown the function belongs to $E$), integration is undecidable. This already shows that integration is harder than derivation (the statement depending of course on the class of functions we want to integrate). 
Observation: The undecidability of integration for the $E$ above is of course deeply related to having function-symbols in $E$ without primitive function-symbol in $E$. This trivially disappears if we close $E$ by throwing in it symbols for each primitive. On the other hand, the inconvenience is that this makes $E$ not being generated by finitely many symbols. This makes the problem of detecting when a function is represented by a symbol in $E$ even more complex. So, the reason why for this large $E$, if we are given a function which we know is in $E$ we can compute its integral, is because we are pretty much assuming that we can by assuming that the input is in $E$.
It remains then the question:
Question: How small can $E$ be such that integration is harder than derivation?
A: I hesitate to answer again, but I agree with comments by Deane Yang and others that so far the discussions haven't quite gotten to the bottom of things. (Not that I promise to succeed in doing so now, but let's see what happens.) 
In a nutshell, you could say that differentiation succeeds largely because 


*

*The derivative is a functor.
That's a modern-day way of stating the chain rule. One way to make this precise is by defining the derivative as a functor from the category of pointed smooth manifolds to the category of vector spaces, taking $f: (M, x) \to (N, y)$ to the linear map $Df_x: T_x M \to T_y N$ between the tangent spaces. The chain rule for smooth maps is exactly the statement that $D$ is functorial. 
Better yet, it's a product-preserving functor. This is nice because it allows you to get at derivatives of other algebraic operations; for example, the product of two functions $f, g: \mathbb{R} \to \mathbb{R}$ is a composite 
$$\mathbb{R} \stackrel{\Delta}{\to} \mathbb{R} \times \mathbb{R} \stackrel{f \times g}{\to} \mathbb{R} \times \mathbb{R} \stackrel{\text{mult}}{\to} \mathbb{R}$$ 
and so to derive the product rule, you just have to know how to take the derivative of that last map $\text{mult}$, and the product-preserving functoriality can take care of the rest. 
Notice by the way that this point of view meshes very well with how Terry Tao emphasized the local aspects of differentiation; presently, the locality was handled by working with pointed manifolds. One can take this a little further and claim "morally" that the derivative functor is represented by a very local object (i.e., an object with one point), sometimes called "the walking tangent vector". This would be something like 
$$T = Spec(\mathbb{R}[x]/(x^2))$$ 
so that the tangent bundle of a manifold $M$ is the manifold of smooth maps $T \to M$. Suffice it to say that all this can be effectively formalized in synthetic differential geometry (SDG), where in fact the category of manifolds can be fully embedded in a suitable smooth topos $\mathcal{T}$, and the derivative functor becomes an internal hom-functor 
$$(-)^T: \mathcal{T} \to \mathcal{T}$$
So in summary, the derivative functor is represented by a local object, and this representability can be regarded as "explaining" the product-preserving functoriality (insofar as representable functors preserve products). 
All this is to suggest that the motto "integration is inverse to differentiation" might be adopting a very misleadingly narrow view of what differentiation is. In the present context, I think we were considering primarily the case of real-valued functions on an interval, but this masks the fact that the derivative is something far more general and functorial and representable on a larger category. 
I am having a hard time understanding integration in anything like these terms, so I'm thinking this could be suggestive of what's going on here. 
A: The reason is entirely that the product rule for differentiation allows you to compute the derivative of a product by induction on the factors.  Many of the "hard" integrals you probably have in mind are constructed from polynomials, exponentials, and logarithms by composition and the algebraic operations (meaning that they are "elementary" in the sense that Todd Trimble discusses), so by using the chain rule, in the form of u-substitution, you can reduce their computation to integrating lots of products whose terms are individually easy integrals.  If something like the product rule existed, this would be doable, but the fact that
$$\int e^{-x^2} dx = \int e^{-u} \frac{1}{2\sqrt{u}} du$$
is not elementary means that there is no hope of such a convenient method.
A: [Edit: belatedly, I realize that Todd has already mentioned the Risch algorithm in his own answer. Cutting this own down to the appropriate essentials.]
I do take exception to your statement that integration is not automated or implemented in CAS software. The Risch Algorithm   is a lot more complicated than derivation (which used to be a routine project to assign to computer science students); I don't know that any CAS fully implements the algorithm, though all of them implement it at least partially; and this is about as good as it gets since there are elementary functions that do not admit elementary primitives.
On another note, I've heard integration referred to as an inverse problem by analysts; unfortunately, I couldn't find a good reference. But the idea was that direct problems and inverse problems are fundamentally different animals with different features. Direct problems (derivation, checking that a function satisfies an DE, multiplication of integers) have unique solutions that have simple algorithms. Inverse problems (integration, solving ODEs, factorization of integers) usually arise when you take a direct problem backwards, and this almost dooms them to being more complicated. Usually, even proving that a solution exists is an achievement, the solutions may be harder to get to, and usually are not unique. 
A: (I've split this off from my original answer, as it is unrelated to that answer.)
A counting (or entropy) argument can also be used to heuristically indicate why inverting differentiation should not be easy.  One can empirically verify that if one differentiates an elementary function of complexity N (i.e. it takes N mathematical symbols in order to describe it), one usually obtains an elementary function of complexity greater than N.  (Polynomials are an exception to this rule, but they are virtually the only such exception.  Not coincidentally, polynomials are one of the rare subclasses of elementary functions for which integration is easy.)  If differentiation was invertible within the class of elementary functions, this would suggest that if one integrated a typical elementary function of complexity at most N, one should get an elementary function of complexity strictly less than N.  (This is unfortunately not a rigorous implication, because the notion of "typical" need not be preserved by differentiation or integration, but let us suspend this issue for the sake of the heuristic.)  But there are significantly more functions in the former class than the latter (the number of functions of a given complexity grows exponentially in that complexity), a contradiction.
Note though that the above argument is quite far from rigorous.  There are certainly many operations (e.g. inverting a large square matrix) such that both the operation and its inverse (which, in the case of matrix inversion, is itself) map bounded complexity objects to bounded complexity objects, and typically increase complexity.  However, it does suggest that in the absence of any particular reason to believe that inversion is easy, the default assumption should be that inversion is hard.
A: Todd Trimble's (fantastic) answer is the clear limiting factor as to why integration is harder in this setting.  But I think this leaves the OP scratching his head: why do we take the point of view that differentiation is the basic operation and integration is the inverse?  The answer is that there is a good reason it is harder but that people still take this point of view.
One could attempt to take the opposite point of view and assume integration is the "basic" operation and that differentiation is the opposite of integration; the basic question is then: given a function $g$, when do we have an $f$ such that $g(x)=C+\int_0^xf(t)dt$?  The answer is: whenever $g$ is absolutely continuous.  This property is quite a bit stronger than regular continuity and also quite a bit more difficult to check (unless $g$ were Lipschitz, say).  Continuity allows you to check each point, but for absolute continuity one essentially has to look at all points in an interval simultaneously.  Thus transferring theorems about integrals to theorems about derivatives is more delicate.  
Even so, this is in many ways the "modern" view of the derivative in analysis, e.g. Sobolev spaces, weak solutions to differential equations, and so on.  The derivative is such a poorly behaving operator that it is actually more convenient to take this approach.
A: I thought about this issue some time ago and I reached an interesting point of view I think. I believe it is worth to share it here. Of course it may be naive. Please feel free to comment.
Integration (antiderivation if you like) is not a "mapping" between a function and another function of the same dimensionality. After each integration a new "constant" appears. This new constant is a new degree of freedom or dimension.
From the recursive point of view this is very important I believe. Sometimes when you integrate (e.g. polynomials and exponentials/sin/cos) the new constant falls into the same family of functions that contained the original functions. For example, a constant is just a polynomial of degree zero or an exponential with zero "growing rate/frequency" (ie exp(0.x) = const. and cos(0.x)=1).
Notice also that the family of polynomials and exponentials are preserved by summation and multiplication. Polynomials also by function composition. So even a priory complicated expressions are just "solved" using the same procedure by recursion.
Now, when because of the new constant you fall outside of this family, for instance: exp(exp(x) + cte) is not in the same family as exp(x), then you need to grow your family and so your recursive method is more complicated. It may happen (in principle) that the (extended) family is infinite and so you cannot find a method at all! You just need a bible :).
In my view the new constants allow us to put more and more information about the real world into the expression (initial conditions, boundary conditions, some physical parameters, etc). Some times this constants are meaningless or do not have physical consequences. Other times they are physically important because your physical system increased in complexity due to this new constant. The new constant expanded the family of functions! More over, from a statistical point of view, sometimes a large number of integration constants are just equivalent to noise. In this case the microscopic description may be impractical but a macroscopic statistical description may be obtained. Furthermore, the aggregate contribution of the constants to some "macroscopic/statistical" quantities is incoherent and so the particular values of the constants are washed out.
In other cases, where complex systems as living systems reside, the integration constants are very important and cannot be ignored or "statistically reduced" to a small number. Using the words of Philip W Anderson more is different in this sense. These new integration constants sum up coherently and complexity arises.
Best Regards,
Juan I. Perotti
A: "Inverse" does not always mean "symmetric". It is pretty mechanical to map $x\mapsto x^3+x^2-5$, and it was an art of 16th century to find an $x$ which maps, say, to $0$.
Or, less mathematical, it is easy to mix a glass of rice with a glass of oats, and it is pretty more a matter of art to get them back to proper glasses.
A: Of course, I voted Todd Trimble's answer, but I want to address an other aspect of the question. 
Somehow, integration is not the inverse of differentiation. If $f:(a,b)\mapsto\mathbb R$ is differentiable, its derivative at each point $x$ is well-understandable, but $f'$ might be ugly as a function. A. Denjoy characterized (or tried to characterize ?) the functions $g:(a,b)\rightarrow\mathbb R$ that are derivatives of everywhere differentiable functions $f$. He used transfinite induction to resconstruct $f$ from $f'$. Of course, integration provides the answer when $g$ is continuous, or integrable, but not in general.
Example. If $\alpha\ge1$, the function $x\mapsto x\sin\frac1{x^\alpha}$ is differentiable everywhere, yet its derivative is not integrable. I am sure that there are much worse examples, where $f'$ is not integrable on any non-trivial interval. The only necessary conditions I see about the derivative $f'$ of an everywhere differentiable function are


*

*$f'$ is measurable, because it is the pointwise limit of a sequence of continuous functions (the quotients),

*$f'$ satisfies the intermediate value property: if $c\in(f'(x),f'(y))$ then there exists a $z$ between $x$ and $y$ such that $f'(z)=c$. This follows from Rolle's Theorem.

A: Todd Trimble's answer that the derivative in the disguise of the tangent mapping is a functor is the perfect answer. 
But I want to elaborate a little also on his first answer:


*

*What are elementary functions?


An answer that I often gave in introductory courses is: Solutions of linear ODEs with specal  constant (integer?) coefficients of low order.
If we would give names to solutions of corresponding integral equations, maybe then  formal integration would look easier, as it is numerically. 
Answer to the comment:
From elementary functions (maybe better, functions with names) we construct other functions by composition, etc. These we want to integrate.
For formal integration we could consider expressions like 
$df = f'dx$ with the usual rules; in particular 
$d(f\circ g) = (f'\circ g) g' dx$ and integration by parts $d(fg) = f.dg + g.df$ 
Call anything of the form $df$ a total differential. 
Then the game is: Reduce it to a sum of total differentials.
Then remove all $d$'s, and you integrated the given 1-form $fdx$.
Let me paraphrase this as: Formal integration is a cohomological operation
(or anti-operation).
A: One relevant thing here is that you are referring to differentiating and integrating within the class of so-called elementary functions, which are built recursively from polynomials and complex exponential and logarithmic functions and taking their closure under the arithmetic operations and composition. Here one can argue by recursion to show that the derivative of an elementary function is elementary, but the antiderivatives might not be elementary. This should surprise one no more than the fact than the square of a rational number is rational, but the square root of a rational number might be irrational. (The analogy isn't completely idle, as shown by differential Galois theory.) 
In other words, the symmetry you refer to is really based on much wider classes of functions (e.g. continuous and continuously differentiable functions), far beyond the purview of the class of elementary functions. 
But let's put that aside. The question might be: is there a mechanical procedure which will decide when an elementary function has an elementary antiderivative (and if it does, exhibit that antiderivative)? There is an almost-answer to this, the so-called Risch algorithm, which I believe is a basis for many symbolic integration packages. But see particularly the issues mentioned in the section "Decidability". 
There is another interesting asymmetry: in first-order logic, derivatives are definable in the sense that given some expansion of the structure of real numbers, say for example the real numbers as an exponential field, the derivative of a definable function is again definable by a first-order formula. But in general there is no purely first-order construction of for example the Riemann integral (involving quantification over finer and finer meshes). I seem to recall that there are similar difficulties in getting a completely satisfactory notion of integration for recursively defined functions on the surreals, due in part to the incompleteness (i.e., the many holes) in the surreal number line. 
A: I want to try a different way of answering the question of why differentiation is somehow the "primary" operation and anti-differentiation the inverting operation. I'll try to make it as elementary as possible.
First let me say what I don't count as an answer. (This is not supposed to be a new contribution to the discussion -- just making my starting point explicit.) It's not enough to point out that differentiation obeys the product and chain rules and explicit differentiability of 1/x (thereby giving the quotient rule as well) and that anti-differentiation doesn't. Somehow one wants an answer that explains why we should have expected this in advance. I was going to say something about differentiation tending to simplify functions, but then realized that that's not really true: it may be true for polynomials but there are lots of functions for which it's false.
The small suggestion I wanted to make was to discretize the question and think about summation versus taking difference functions. Here the situation is slightly confusing because expressions like $\sum_{n=1}^Nf(n)$ tend to come up more often than expressions like $f(n)-f(n-1)$. But let's forget that and think about what it is that we have to do if we want to work out $\sum_{n=1}^Nf(n)$ explicitly. Usually we need to guess a function g and prove that $g(n)-g(n-1)=f(n)$ for every $n$, from which it follows by induction that $g(N)=\sum_{n=1}^Nf(n)+g(0)$. This (the finding of the function $g$) is a discrete analogue of anti-differentiating.
Looked at this way, to work out the sum we have to solve the functional equation $g(n)-g(n-1)=f(n)$ (where we are given $f$ and are required to solve for $g$). By contrast, when we work out the difference function we are solving the similar looking, but much easier, functional equation $g(n)=f(n)-f(n-1)$. It's much easier because the unknown function is involved only once: indeed, in a sense there's nothing to solve at all, but experience shows that we can usually simplify the right-hand side. Of course, with the first equation we can't simplify the left-hand side in a similar way because we don't know what $g$ is. 
It's a bit like the difference between solving the equation $x^2+x=10$ and solving the equation $x=10^2+10$ (that is, the difference between algebra and arithmetic). So here is a real sense, in a closely analogous situation, where one operation is direct and the other is indirect and involves solving for something.
A: I might as well give my very, very vague philosophical take on the discussion so far (which, despite my obvious initial skepticism, has been extremely interesting).
First, from almost any perspective except for symbolic computations, I consider integration to be much easier to work with than differentiation.
As for formal symbolic computations, it appears to me that the point is that on the appropriate space of "functions that can be defined using a formula", the derivative is a linear operator that behaves nicely with respect to other natural operations, notably composition, multiplication, and division. On the other hand, the antiderivative operator (say, with some fixed initial condition) is a linear operator that does not have the same nice formal algebraic properties.
But of course this begs the question of why is this so. Trimble, Tao, and Gowers have posted very beautiful interesting answers, but I'm still not sure I get it. One important point, I think, is that differentiation arises via linearization, which is somehow a simplification (since at heart you're replacing a nonlinear function by a linear one). On the other hand, even though integration is also a linear operation, it arises through "antilinearization", which is somehow an "anti-simplification" (since at heart you're reconstructing a nonlinear function from all of its linear approximations).
A: Why is integration harder for people than differentiation?  This is as much a question about people and perception than it is about mathematics.  Methods are ad hoc for the integrations that inspired the question, while software, for example Mathematica, uses rules to integrate that are just as mechanical as its rules for differentiation, as 
Stephen Wolfram explains in his book A New Kind of Science.
But performing the integration is only half the issue.  The other half is making the answer look right, and for that the computer has to perform algebraic simplifications.  This need for algebra is somehow intrinsic to these problems, e.g., even to verify an answer that looks different.  So in a sense its difficulties are not different from the calculus student who needs to do algebra.
Why then is algebra hard, in particular algebraic simplification?  Without getting too theoretical, just consider a typical adhoc procedure to integrate x^2*Exp[x].  We know that taking the derivative of x^n*Exp[x] gives two terms, and we can use that knowledge to predict the answer will be a combination of  x^2*Exp[x], x*Exp[x], and Exp[x].  The behavior there allows us to solve for an answer.
Let's abstract from this example, where the terms are just linearly independent.  The presence of terms is a binary condition, and one can think of taking the derivative as an operation like a cellular automaton.  So an abstract model of the derivative operator is a cellular automaton.  
Now that one has a model it is possible to investigate questions like the original question.  Some cellular automata are reducible, in the same way that integrating x^n*Exp[x] is reducible, while others are irreducible and undecidable questions (i.e. there is no decision procedure) about them are common.  So in the end it is basically the NKS phenomenon that Wolfram discovered. 
A: For me it s like having a puzzle. Differentiation is taking the final picture assembled and putting into the box, integrating is taking the pieces from the box and assemble it.
The key fact of this analogy is the chain rule and that the multiplication is commutative:
$$
(\phi_1 \circ \phi_2 \circ\cdots \circ \phi_n)'(x)=\prod_{k=1}^n \phi_k'(\phi_{k+1}\circ \cdots \circ \phi_{n})(x), 
$$
among the $n!$ different permutations for the product, most of them will not allow to perform the integration straightforward.
