Abstract
Given a string, what is its complexity? We survey what is known about the computational complexity of this problem, and describe several open questions.
- Title: Subtitle
- The Complexity of Complexity
- Creators
- Eric Allender (Author) - Computer Science (New Brunswick), Rutgers University
- Contributors
- Adam Day (null)Michael Fellows (null)Noam Greenberg (null)Bakhadyr Khoussainov (null)Alexander Melnikov (null)Frances Rosamond (null)
- Publication Details
- Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, pp.79-94
- Date published
- 2017
- Publisher
- Springer-Verlag
- Number of pages
- 17 p.
- Grant note
- National Science Foundation - CCF-1555409
- Academic Unit
- School of Arts and Sciences; Computer Science (SAS)
- Language
- English
- Resource Type
- Book chapter
- Comment
- Lecture Notes in Computer Science, Volume 10010.
- Identifiers
- 991031549873504646