Two types of properties for complexity measures

DOI10.1016/0020-0190(81)90109-5zbMath0474.68060OpenAlexW2014685228MaRDI QIDQ1158961

Gerhard Lischke

Publication date: 1981

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(81)90109-5

zbMATH Keywords

optimalityparallel computationminimalitypropernessconservationconformitydensenesscomplexity classesrecursive enumerabilityBlum measuresclosure under intersectionfinite invariancequasiminimality, quasioptimalitystep counting functionst- presentability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• Unnamed Item
• The enumerability and invariance of complexity classes
• Über die Erfüllung gewisser Erhaltungssätze durch Kompliziertheitsmasse
• Natürliche Kompliziertheitsmasze und Erhaltungssätze II
• Classes of computable functions defined by bounds on computation
• A Machine-Independent Theory of the Complexity of Recursive Functions
• A note on dense and nondense families of complexity classes
• An Overview of the Theory of Computational Complexity
• Recursive Properties of Abstract Complexity Classes

This page was built for publication: Two types of properties for complexity measures