Making sense of language is an NP-complete problem, which seems like something you might intuitively guess, but you can prove this by reducing the well known NP-complete problem of graph $k$-coloring to the anaphora agreement problem in linguistics.