"Proof of Non-Work" would be a very interesting concept, although I can't think of a way to do it. (In a sense, Proof of Work is an expensive method to accomplish Proof of Non-Work.)