Are there Conservation Laws in Complexity Theory? Let me start with some examples. Why is it so trivial to show CVP is in P but so hard to show LP is in P; while both are P-complete problems. 

Or take primality. It is easier to show composites in NP than primes in NP (which required Pratt) and eventually in P. Why did it have to display this asymmetry at all? 

I know Hilbert, need for creativity, proofs are in NP etc. But that has not stopped me from having a queasy feeling that there is more to this than meets the eye.

Is there a quantifiable notion of "work" and is there a "conservation law" in complexity theory? That shows, for example, that even though CVP and LP are both P-complete, they hide their complexities at "different places" -- one in the reduction (Is CVP simple because all the work is done in the reduction?) and the other in expressibility of the language.

Anyone else queasy as well and with some insights? Or do we shrug and say/accept that this is the nature of computation?

This is my first question to the forum: fingers crossed.

Edit: CVP is Circuit Value Problem and LP is Linear Programming.  Thanks Sadeq, for pointing out a confusion.
This is a question that has run across my mind many times.

I think one place to look is information theory.  Here is a speculation of mine.  Given a problem maybe we can give some sort of entropy value to information given as input and the information received from the algorithm.  If we could do that, then there would be some minimum amount of information gain required by an algorithm to solve that problem.

There's one related thing I've wanted to figure out.  In some NP-complete problems you can find a constrained version in P; with the Hamiltonian path if you specify that the graph is a DAG then there is a p-time algorithm to solve it.  With other problems like TSP, there's often p-time algorithms that will approximate the optimal.  It seems to me, for constrained p-time algorithms, there should be some proportional relationship between the addition information assumed and run-time complexity reduction.  In the case of the TSP we aren't assuming additional information, we're relaxing the precision, which I expect to have a similar effect on any sort of algorithmic information gain.

Note on Conservation Laws

In the earlier 1900's there was little known German-American mathematician named Emily Noether.  Among other things she was described by Einstein and Hilbert to be the most import women in the history of mathematics.  In 1915 she published what is now known as Noether's First Theorem.  The theorem was about physical laws of conservation, and said that all conservation laws have a corresponding differential symmetry in the physical system.  Conservation of Angular Momentum comes from a rotational symmetry in space, Conservation of Linear Momentum is translation in space, Conservation of Energy is translation in time.  Given that, for there to be some law of conservation of complexity in a formal sense, there would need to be some corresponding differential symmetry in a Langragian function.