Complexity of Information Extraction

Author: Abu-Mostafa, Yaser Said

Year: 1983

Degree: Dissertation (Ph.D.)

Advisor: Psaltis, Demetri

Committee Members: Psaltis, Demetri; Kechris, Alexander S.; McEliece, Robert J.; Mead, Carver; Posner, Edward C.; Ryser, Herbert J.; Wilson, Richard M.

Option: Electrical Engineering; Computer Science

DOI: 10.7907/FVKM-7J60

Abstract

This thesis describes a mathematical theory that interrelates the basic concepts of complexity, cost, information and reliability. The accessibility of information, as opposed to its availability, is characterized. Universal bounds for complexity distribution, implementation cost and decision reliability are estimated. These bounds give rise to a methodology for any consistent definition of a complexity measure. The basic notions of pattern recognition and information theory are directly related to computational complexity.

Files