Deterministic versus nondeterministic time and lower bound problems

DOI10.1145/602382.602409zbMath1326.68166OpenAlexW1970149677MaRDI QIDQ3455557

Richard E. Stearns

Publication date: 7 December 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/602382.602409

zbMATH Keywords

computational complexityNP-completenessgeneric algorithmstime complexitynondeterminismpower indexSATgeneric problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Refining complexity analyses in planning by exploiting the exponential time hypothesis

This page was built for publication: Deterministic versus nondeterministic time and lower bound problems