Sophistication Revisited

• Type: Article in International Scientific Journal
• Date: 2009

Authors

antunes, l (Author) FCUP; fortnow, l (Author) Other

Journal

Title: Theory of Computing Systems

Vol. 45

Pages: 150-161

ISSN: 1432-4350

Publisher: Springer Nature

Indexing

ISI Web of Knowledge - 11 Citations

Scopus - 16 Citations

Other information

Authenticus ID: P-003-JZB

DOI: 10.1007/s00224-007-9095-5

Abstract (EN): Kolmogorov complexity measures the amount of information in a string as the size of the shortest program that computes the string. The Kolmogorov structure function divides the smallest program producing a string in two parts: the useful information present in the string, called sophistication if based on total functions, and the remaining accidental information. We formalize a connection between sophistication (due to Koppel) and a variation of computational depth (intuitively the useful or nonrandom information in a string), prove the existence of strings with maximum sophistication and show that they are the deepest of all strings.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 12