On completeness under random reductions

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

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

Recommendations

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

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 (6)

• 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
• Title not available (Why is that?)

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)