scientific article; zbMATH DE number 3446413

MaRDI QIDQ4770482zbMATH OpenFDO

Authors K. Mehlhorn

Publication date 1974

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Other degrees and reducibilities in computability and recursion theory (03D30)

Cited in

(9)

• Pseudorandom sources for BPP
• Computational depth and reducibility
• Almost everywhere high nonuniform complexity
• The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
• Polynomial and abstract subrecursive classes
• An upward measure separation theorem
• Equivalence of measures of complexity classes
• Effective category and measure in abstract complexity theory
• Nondiamond theorems for polynomial time reducibility

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 Q4770482)