Share Email Print

Proceedings Paper

Computational complexity of synthesizing target recognition programs
Author(s): Michael A. Zmuda; Mateen M. Rizki; Louis A. Tamburino
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

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.

Paper Details

Date Published: 9 July 1992
PDF: 7 pages
Proc. SPIE 1699, Signal Processing, Sensor Fusion, and Target Recognition, (9 July 1992); doi: 10.1117/12.138229
Show Author Affiliations
Michael A. Zmuda, Wright State Univ. (United States)
Mateen M. Rizki, Wright State Univ. (United States)
Louis A. Tamburino, Air Force Wright Lab. (United States)

Published in SPIE Proceedings Vol. 1699:
Signal Processing, Sensor Fusion, and Target Recognition
Vibeke Libby; Ivan Kadar, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?