scientific article; zbMATH DE number 1542049

MaRDI QIDQ4520107zbMATH OpenFDO

Authors Gerd Wechsung

Publication date 11 December 2000

zbMATH Keywords

computational complexitycomplexity classesreducibilitycompletenesspolynomial hierarchyBoolean hierarchyhighnesslownessleaf languagesdeterminism versus nondeterminismprobabilistic complexity classescounting classestime versus spacecomplexity classes of functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 192916
• Theory of computation.
• scientific article; zbMATH DE number 44418
• Computational Complexity
• Publication:4942157

Cited in

(6)

• Complexity theory. Limits of the efficiency of algorithms
• Observations on complete sets between linear time and polynomial time
• Basic complexity
• scientific article; zbMATH DE number 3936519 (Why is no real title available?)
• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• Arithmetic theories for computational complexity problems

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4520107)