One of the advantages of cryptocurrencies like Bitcoin that is often repeated is how hard it should be to manipulate past transactions. The reason that is often stated is that you would have to re-calculate all the headers with all the hash values of the whole chain which is practically un-doable.
My question is: How do you verify the blockchain integrity? Don't you also have to recalculate all the values to see whether they are valid? Or is the complexity class of verification different from creating a new chain? In other words is there some asymmetry at work here and if yes how does it work?