Sometimes a blockchain application needs to perform an operation, such as a scrypt verification, that is extremely computationally expensive. Are there any techniques that can help me design around this problem so that my application doesn't have to pay enormous fees?
Yes, there are! Although the Ethereum scripting language is Turing Complete and therefore able to perform any possible computation, there is a simple way to remove many types of difficult computation from having to be performed directly on the blockchain itself, by making use of deposits, challenges and verifications.
Take the example of verifying a scrypt operation. My application might have some data, and it wants to know what the scrypt hash of that data is in order to compare it against a reference or to check a certain property of the hash (for a mining algorithm, perhaps). Instead of computing the hash immediately, the application can instead allow anyone to submit the hash of the data themselves, along with a deposit. The purpose of the deposit is so that submitter can be penalised if they submit an inaccurate hash, and for the sake of our example let's assume the deposit is large enough to cover the cost of computing the operation on the blockchain if necessary, in addition to the penalty.
Next, the application holds a challenge period so that external observers have a chance to check on their own machines if the data in fact hashes to the claimed value. Because this operation is performed by only a few observers instead of the entire blockchain, this is a total savings in terms of resources. During the challenge period, if any of the observers discovers that the submitted hash is inaccurate, they submit a transaction to that effect containing their own counter-deposit. Again we can assume for the sake of our example that the deposit is large enough to cover the costs of verifying the hash on chain.
Now the application merely needs to check the result and return the remainder of the deposits to the party who was proved correct, along with an additional reward of some kind for a correct hash. Or, if no challenge was submitted during the challenge period, the application can merely return the reward along with the deposit to the original user, without performing any verification. With this technique, users who submit correct hashes or challenges receive a reward for their efforts, and if they submit incorrect hashes (or incorrect challenges) they pay a large penalty. The incentives ensure that any misbehaviour is a losing strategy, and the application developer themselves can play the role of both submitter and challenger to ensure the application operates as desired. Because observers will not pursue losing strategies, the application will almost never have to actually verify the hash.
An advanced version of this technique would give the "caught" submitter with an incorrect hash an opportunity to "fess up" in return for a lower penalty, so that even in the event an invalid hash is submitted, verification will not need to be actually performed.
More elaborate techniques are also possible involving zero knowledge proofs, but this basic deposit-challenge-verification approach requires no complicated mathematics, and incurs a lower computational cost than most zero knowledge proof techniques.