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

zbMATH Open0833.03014MaRDI QIDQ1901894FDOQ1901894

Authors: Yanyan Li 

Publication date: 3 January 1996

Published in: Russian Mathematics (Search for Journal in Brave)

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

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)

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

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)