The Program Understanding Problem:
Analysis and A Heuristic Approach
Steven Woods and
Qiang Yang.
Abstract
Program understanding is the process of making sense of a complex
source code. It has been considered as computationally difficult and
conceptually complex. So far, no formal complexity results have been
presented, and conceptual models differ from one researcher to the
next.
In this paper we formally prove that program understanding is NP-hard.
Furthermore, we show that even a much simpler subproblem remains
NP-hard. However, we do not despair by this result, but rather, offer
an attractive problem-solving model for the program understanding
problem. Our model is built on a framework for solving Constraint
Satisfaction Problems, or CSPs, which are known to have interesting
heuristic solutions. Specifically, we can now heuristically address
program understanding through constraint propagation and search
algorithms.
Copyright Notice
Copyright 1996 IEEE. Published in the Proceedings of the 18th
International Conference on Software Engineering (ICSE-18), March
25-29, 1996, Berlin, Germany. Personal use of this material is
permitted. However, permission to reprint/republish this material for
advertising or promotional purposes or for creating new collective
works for resale or redistribution to servers or lists, or to reuse
any copyrighted component of this work in other works, must be
obtained from the IEEE.
The Paper (10 pages)