A New Proof of The Np-Completeness of Visual Match
R.A. Rensink, Department of Computer Science, University of British Columbia, Vancouver, Canada.

UBC CS Technical Report 89-22 (September 1989).

Abstract

A new proof is presented of Tsotsos' result 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 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.

Back to main publications list.