On completeness under random reductions

DOI10.1006/JCSS.1996.0086zbMATH Open0869.68028OpenAlexW2029653092MaRDI QIDQ676458FDOQ676458

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)

Cited In (5)

• Strong Medvedev reducibilities and the KL-randomness problem
• Random reduction consistency of the Weber set, the core and the anti-core
• Completeness for nondeterministic complexity classes
• Saving queries with randomness
• ON RELATIVE COMPLETE REDUCIBILITY

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)