Exact Pairs for Abstract Bounded Reducibilities

DOI10.1002/MALQ.19990450306MaRDI QIDQ4264535zbMATH OpenOpenAlexFDO

Authors Wolfgang Merkle

Publication date 9 May 2000

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.19990450306

zbMATH Keywords

abstract reducibilitiesexact pairsminimal pair of recursive setsresource bounded reducibilities

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30)

Cites work

• A Machine-Independent Theory of the Complexity of Recursive Functions
• An observation on probability versus randomness with applications to complexity classes
• Classical recursion theory. The theory of functions and sets of natural numbers
• scientific article; zbMATH DE number 1115674 (Why is no real title available?)
• scientific article; zbMATH DE number 761756 (Why is no real title available?)
• On the Structure of Polynomial Time Reducibility
• On the theory of the PTIME degrees of the recursive sets
• Polynomial and abstract subrecursive classes
• Separations by random oracles and ``almost classes for generalized reducibilities
• Sublattices of the polynomial time degrees
• The recursion-theoretic structure of complexity classes

Cited in

(2)

• Joint reductions, tight closure, and the Briançon-Skoda theorem
• scientific article; zbMATH DE number 1086677 (Why is no real title available?)

This page was built for publication: Exact Pairs for Abstract Bounded Reducibilities

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