Which problems have strongly exponential complexity?

DOI10.1006/jcss.2001.1774zbMath1006.68052WikidataQ55891730 ScholiaQ55891730MaRDI QIDQ1604206

Francis Zane, Ramamohan Paturi, Russell Impagliazzo

Publication date: 4 July 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.2001.1774

zbMATH Keywords

NP-complete problems; sub-exponential reduction family

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)