diff is a np problem and a real np problem in that most (all?) implementations are not good enough for everyday use. You will regularly get situations where it

diff is a np problem and a real np problem in that most (all?) implementations are not good enough for everyday use. You will regularly get situations where it fails. Compared to most np problems that just sit in a lab where they save a dollar on a working multi million operation by adding $$ worth of complexity. It'd be interesting to see all the diff's of the world in an arena battling it out. Computer Science seems unable to invent new things since 1980 so we should be improving on what they discovered at least.