The Exact Hardness of Deciding Derivational and Runtime Complexity.

Andreas Schnabl Jakob Grue Simonsen

Published in: CSL (2011)

Keyphrases

computational complexity
worst case
decision problems
np hardness
real time
real world
data structure
finite state
search space
probabilistic model
information theoretic
phase transition