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".

"Death by ironic circumstances. Time of death chosen from within the allowed range such that hazards to bystanders are minimized, then such that irony is maximized, then randomly."

Solving for maxima in the Law of Universal Perversity should do it.

Might as well wish for a Deathnote that was Touring Complete.

The story emphasises that Deathnotes are fairly literal, and that if you try to push it you'll just get a heart attack death.

"Death by starvation while yelling repeatedly the solution to the P=NP problem or if a solution is possible"

You just cause an exception in the Deathnote implementation code and crashed the universe...