I think the comparison to NP-completeness is very apt. Will have to borrow that one.