9 July 1992 Computational complexity of synthesizing target recognition programs
Author Affiliations +
An important research objective is to develop systems which automatically generate target recognition programs. This paper presents evidence that such general goals are not feasible. Specifically, the problem of automatically synthesizing target recognition programs is shown to be NP-Complete. The intractability of this problem motivates a problem specification which is tolerant of errors. Although easier, this too is shown to be NP-Complete. These results indicate that automatic target recognition has computational limitations which are inherent in the problem specification, and not necessarily a lack of clever system designs.
© (1992) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Michael A. Zmuda, Mateen M. Rizki, Louis A. Tamburino, "Computational complexity of synthesizing target recognition programs", Proc. SPIE 1699, Signal Processing, Sensor Fusion, and Target Recognition, (9 July 1992); doi: 10.1117/12.138229; https://doi.org/10.1117/12.138229


Image enhancement for automatic target detection
Proceedings of SPIE (July 25 2002)
Neural Networks For Adaptive Shape Tracking
Proceedings of SPIE (September 05 1989)
HEATR project: ATR algorithm parallelization
Proceedings of SPIE (September 15 1998)
Comparison of three scheduling algorithms
Proceedings of SPIE (December 09 1997)

Back to Top