[soheil]

Take SETI for example. If you find an earth like planetoid in a very precise region of sky which takes a long time to sift through pictures of the sky to find then you can just give the coordinates of that point for other nodes to verify. This could be the PoW algorithm.

[bastawhiz]

That's problematic, though. You have a fixed computational difficulty (difficulty can't be scaled up or down).