The Complexity of Complexity

Allender, E

Allender, E (reprint author), Rutgers State Univ, Dept Comp Sci, Piscataway, NJ 08854 USA.

COMPUTABILITY AND COMPLEXITY: ESSAYS DEDICATED TO RODNEY G. DOWNEY ON THE OCCASION OF HIS 60TH BIRTHDAY, 2017; 10010 ( ): 79

Abstract

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

Full Text Link