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.