I've read here and there, perhaps incorrectly, that the transaction fees depend on the size of the transaction (in bytes). However, with smart contracts, the difficulty to process a transaction is not proportional to its size: for example, there are small SAT-problem that can never be solved in practice, while it is very easy to answer the query "find the first byte of the sequence ab55..." even if the sequence is huge. Obviously, there should be some cost for the size of the transaction as it has to be stored on-chain, but if the cost is only on the size of the transaction, and not on the complexity of the request, then the chosen memory-time trade-offs will be greatly in favor of using time (free) above using memory (costly).
So, what will be the incentive mechanism for fees in cardano?