Heap Typability is NP-CompleteHeap Typability is NP-CompleteThis 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.