Technical Reports

The ICICS/CS Reading Room

UBC CS TR-89-22 Summary

A New Proof of the NP Completeness of Visual Match, September 1989 R. Rensink

A new proof is presented of Tsotsos' result [1] that the VISUAL MATCH problem is NP-complete when no (high-level) constraints are imposed on the search space. Like the proof given by Tsotsos, it is based on the polynomial reduction of the NP-complete problem KNAPSACK [2] to VISUAL MATCH. Tsotsos' proof, however, involves limited-precision real numbers, which introduces an extra degree of complexity to his treatment. The reduction of KNAPSACK to VISUAL MATCH presented here makes no use of limited-precision numbers, leading to a simpler and more direct proof of the result.

If you have any questions or comments regarding this page please send mail to