Correlation of NP-sets and co-NP-sets with respect to a random oracle

MaRDI QIDQ1901894zbMATH OpenFDO

Authors Yanyan Li

Publication date 3 January 1996

Published in Russian Mathematics (Search for Journal in Brave)

zbMATH Keywords

random oracleNPco-NP

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 1555920
• scientific article; zbMATH DE number 4049050
• On random hard sets for NP
• On random oracle separations
• Relative to a random oracle, NP is not small

Cited in

(3)

• The Complexity of Problems in P Given Correlated Instances
• On the classification of NP-complete problems in terms of their correlation coefficient
• scientific article; zbMATH DE number 1555920 (Why is no real title available?)

This page was built for publication: Correlation of NP-sets and co-NP-sets with respect to a random oracle

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