The structure of relativized P and NP questions

MaRDI QIDQ582906zbMATH OpenFDO

Authors Hong Ye

Publication date 1988

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

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)

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

Cited in

(3)

• Oracle‐Constructions to Prove All Possible Relationships Between Relativizations of P, NP, EL, NEL, EP and NEP
• Relativized separation of EQP from \(\text{P}^{\text{NP}}\)
• 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)