Computational complexity of synthesizing target recognition programs

Michael A. Zmuda; Mateen M. Rizki; Louis A. Tamburino

doi:10.1117/12.138229

9 July 1992 Computational complexity of synthesizing target recognition programs

Michael A. Zmuda, Mateen M. Rizki, Louis A. Tamburino

Proceedings Volume 1699, Signal Processing, Sensor Fusion, and Target Recognition; (1992) https://doi.org/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.

Citation Download Citation

Michael A. Zmuda, Mateen M. Rizki, and Louis A. Tamburino "Computational complexity of synthesizing target recognition programs", Proc. SPIE 1699, Signal Processing, Sensor Fusion, and Target Recognition, (9 July 1992); https://doi.org/10.1117/12.138229

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available