On the complexity-relativized strong reducibilities

DOI10.1007/BF01063845MaRDI QIDQ800353zbMATH OpenFDO

Authors Jari Talja

Publication date 1983

Published in Studia Logica (Search for Journal in Brave)

zbMATH Keywords

orderingstrong recursive reducibility classes

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• Publication:4934278
• On bounded \(m\)-reducibilities
• Strong polynomial-time reducibility
• Sub-Turing reducibilities of restricted complexity
• scientific article; zbMATH DE number 1531931

Cites work

• scientific article; zbMATH DE number 3715538 (Why is no real title available?)
• scientific article; zbMATH DE number 3586480 (Why is no real title available?)
• scientific article; zbMATH DE number 3431764 (Why is no real title available?)
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Strong reducibilities

Cited in

(8)

• scientific article; zbMATH DE number 1747699 (Why is no real title available?)
• A solution to Curry and Hindley's problem on combinatory strong reduction
• Strong isomorphism reductions in complexity theory
• scientific article; zbMATH DE number 176750 (Why is no real title available?)
• ON RELATIVE COMPLETE REDUCIBILITY
• Strongly reducing variants of the Krivine abstract machine
• On the power of deterministic reductions to C=P
• scientific article; zbMATH DE number 4119625 (Why is no real title available?)

This page was built for publication: On the complexity-relativized strong reducibilities

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