Thanks for your comments; this is the sort of discussion I was looking for.
One problem with the above is that you'd need 16GB of storage to check block validity, even for SPV clients on things like cell phones. So that's one problem that would need to be fixed.
Maybe if the r-value (number of rounds) were really low and only a small fraction of the memory cells wound up being read from the block header could include some kind of map showing which memory cells got hit during the hashing operation. Then with the map a low-memory device could check a hash.
Even better, SPV clients could ask full-chain clients to calculate the map for them so it wouldn't have to be stored in the chain. The point is that giving an SPV client a bogus map won't fool them so there's no trust there.
Scrypt already has the lowest possible r=1.
Sorry, you're right, I got the parameter names mixed up. What I'm talking about doesn't have a separate parameter in the scrypt specification. In scryptROMix step 3:
3. for i = 0 to N - 1 do
j = Integerify (X) mod N
where Integerify (B[0] ... B[2 * r - 1]) is defined
as the result of interpreting B[2 * r - 1] as a
little-endian integer.
T = X xor V[j]
X = scryptBlockMix (T)
end for
There's no reason why that for loop (bolded) has to be from 0..(N-1); the loop could run more or less than N times. That's the parameter (the number of times that loop runs) that I was thinking of reducing. Of course you still have to populate the memory in the first place, which takes N operations, so this isn't a complete solution yet.
You'll need a completely different PoW (i.e. not hashcash based)
Hrm, not hashcash based in what sense? If you mean not in the sense of using a SHA-family function then sure, but Litecoin is already "not hashcash based" in that sense.
whose verification time is constant or growing very slowly (e.g. logarithmic) with increasing memory requirements.
Yes, I certainly agree that this must be true.
I think the key is to have the hash operation h(x) emit some additional small certificate c that a verifier v(x,y,c) can use to confirm that h(x)=y using logarithmic memory -- whereas computing h(x) without the certificate (or y) requires linear memory. So it's a trapdoor function from a space complexity perspective. Surely such a thing must exist; I need to dig the literature.