On the complexity-relativized strong reducibilities

DOI10.1007/BF01063845zbMATH Open0549.03030MaRDI QIDQ800353FDOQ800353

Authors: Jari Talja 

Publication date: 1983

Published in: Studia Logica (Search for Journal in Brave)

Recommendations

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

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)

Cites Work

• A Machine-Independent Theory of the Complexity of Recursive Functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Strong reducibilities

Cited In (8)

• Title not available (Why is that?)
• A solution to Curry and Hindley's problem on combinatory strong reduction
• Strong isomorphism reductions in complexity theory
• Title not available (Why is that?)
• ON RELATIVE COMPLETE REDUCIBILITY
• Strongly reducing variants of the Krivine abstract machine
• On the power of deterministic reductions to C=P
• Title not available (Why is that?)

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)