scientific article; zbMATH DE number 3992933

MaRDI QIDQ4720786zbMATH OpenFDO

Authors Carol Tretkoff

Publication date 1986

zbMATH Keywords

linear spaceseparationself-reducibilitybounded oraclesdeterministic linear timenondeterministic linear time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Complexity classes and sparse oracles
• Borel complexity and Ramsey largeness of sets of oracles separating complexity classes
• scientific article; zbMATH DE number 3978383
• On sparse oracles separating feasible complexity classes
• scientific article; zbMATH DE number 223337
• scientific article; zbMATH DE number 515747
• A general method to construct oracles realizing given relationships between complexity classes
• Polynomial-time random oracles and separating complexity classes
• scientific article; zbMATH DE number 139642

Cited in

(5)

• scientific article; zbMATH DE number 4045155 (Why is no real title available?)
• Complexity, combinatorial group theory and the language of palutators
• Relativized alternation and space-bounded computation
• Complexity classes and sparse oracles
• On quasilinear-time complexity theory

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 Q4720786)