The death has to be possible; Light tests out the limits early and finds IIRC that if you specify an imprisoned criminal dies outside the prison, the Death Note just gives up and kills them normally or something like that. 'Batman' and 'space laser' are right out, as is making criminals solve NP-hard or Halting problems.
What are the odds that three victims would write out notes that combine to encode a message about death gods eating apples? I wouldn't rule out their writing solutions to NP-hard problems. Even halting problem problems. It's just a matter of getting them to write a note that begins with a certain letter, or that includes the word "yes" or "no".
