This research was conducted by Matt Elder and Ben Liblit.

Given a snapshot of a running program’s memory heap, and a set
of types representing data in the program, *dynamic heap type inference*
attempts to assign types to memory locations such that certain
global consistency constraints are satisfied. Previous work has
used brute-force searches to solve heap typing problems. We
prove that a problem derived from dynamic heap type inference is
NP-complete by reduction from 3-colorability. Thus, it is
unlikely that a polynomial-time algorithm for heap type
inference exists.

The full paper is available as a single PDF document. A suggested BibTeX citation record is also available.