scientific article; zbMATH DE number 227415

MaRDI QIDQ5286848zbMATH OpenFDO

Authors Li Xiang

Publication date 1 September 1993

zbMATH Keywords

immunitycounting classescounting complexity classesexponential time complexity classesnumber of accepting pathsrelativized separations

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On relativized exponential and probabilistic complexity classes
• Relativizations comparing NP and exponential time
• Oracles for Deterministic Versus Alternating Classes
• Polynomial-time random oracles and separating complexity classes
• Relativized counting classes: Relations among thresholds, parity, and mods

Cited in

(5)

• On randomized versus deterministic computation
• Relativizations of Unambiguous and Random Polynomial Time Classes
• Towards the Actual Relationship Between NP and Exponential Time
• An explicit separation of relativised random polynomial time and relativised deterministic polynomial time
• On relationships between approximate and probabilistic complexity classes

This page was built for publication:

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