The structure of relativized P and NP questions

zbMATH Open0691.68051MaRDI QIDQ582906FDOQ582906

Authors: Hong Ye 

Publication date: 1988

Published in: Chinese Annals of Mathematics. Series B (Search for Journal in Brave)

Recommendations

• scientific article; zbMATH DE number 4011940
• On relativizations of the P =? NP question for several structures
• scientific article; zbMATH DE number 500314
• Positive relativizations of the \(P=?\) NP problem
• Oracle-dependent properties of the lattice of NP sets

zbMATH Keywords

oraclemitotic setsrelativized P and NP problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Recursively (computably) enumerable sets and degrees (03D25) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (3)

• Relativized separation of EQP from \(\text{P}^{\text{NP}}\)
• Oracle‐Constructions to Prove All Possible Relationships Between Relativizations of P, NP, EL, NEL, EP and NEP
• Oracle-dependent properties of the lattice of NP sets

This page was built for publication: The structure of relativized P and NP questions

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