On completeness under random reductions

DOI10.1006/JCSS.1996.0086MaRDI QIDQ676458zbMATHOpenAlexFDO

Authors Suresh Chari, Pankaj Rohatgi

Publication date 20 August 1997

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcss.1996.0086

zbMATH Keywords

completeness under random reductions

Mathematics Subject Classification ID

Theory of programming languages (68N15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1332675
• Saving queries with randomness
• Random-Self-Reducibility of Complete Sets
• scientific article; zbMATH DE number 3995648

Cited in

(6)

• ON RELATIVE COMPLETE REDUCIBILITY
• Completeness for nondeterministic complexity classes
• Saving queries with randomness
• scientific article; zbMATH DE number 1737510 (Why is no real title available?)
• Strong Medvedev reducibilities and the KL-randomness problem
• Random reduction consistency of the Weber set, the core and the anti-core

This page was built for publication: On completeness under random reductions

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