The Complexity of Complexity

Eric Allender

doi:10.1007/978-3-319-50062-1_6

Back

Book chapter

Peer reviewed

The Complexity of Complexity

Eric Allender

Computability and Complexity, pp.79-94

Lecture Notes in Computer Science, Springer International Publishing

12/01/2016

DOI: https://doi.org/10.1007/978-3-319-50062-1_6

Abstract

Graph Automorphism

Complexity Class

Turing Reduction

Universal Machine

Kolmogorov Complexity

Given a string, what is its complexity? We survey what is known about the computational complexity of this problem, and describe several open questions.

Metrics

5 Record Views

11 Times Cited - Web of Science

Details

Title: The Complexity of Complexity
Creators: Eric Allender - Department of Computer Science, Rutgers University, Piscataway, USA
Publication Details: Computability and Complexity, pp.79-94
Date published: 12/01/2016
Series: Lecture Notes in Computer Science
Publisher: Springer International Publishing; Cham
Academic Unit: Computer Science (SAS)
Language: English
Resource Type: Book chapter
Identifiers: 991031654849204646