Heap Typability is NP-Complete

Abstract

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.

Paper

This paper is available as a PDF document.

Changed 16 May 2008