9 July 1992 Computational complexity of synthesizing target recognition programs
Author Affiliations +
Proceedings Volume 1699, Signal Processing, Sensor Fusion, and Target Recognition; (1992); doi: 10.1117/12.138229
Event: Aerospace Sensing, 1992, Orlando, FL, United States
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.
© (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
PROCEEDINGS
7 PAGES


SHARE
KEYWORDS
Target recognition

Silicon

Automatic target recognition

Information operations

Computability theory

Computer science

Computing systems

Back to Top