Sophistication Revisited

• Tipo: Artigo em Revista Científica Internacional
• Data: 2009

Autores

antunes, l (Autor) FCUP; fortnow, l (Autor) Outra

Revista

Título: Theory of Computing Systems

Vol. 45

Páginas: 150-161

ISSN: 1432-4350

Editora: Springer Nature

Indexação

ISI Web of Knowledge - 11 Citações

Scopus - 16 Citações

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 12