scientific article; zbMATH DE number 3992933

MaRDI QIDQ4720786zbMATH OpenFDO

Authors Carol Tretkoff

Publication date 1986

zbMATH Keywords

bounded oraclesdeterministic linear timelinear spacenondeterministic linear timeself-reducibilityseparation

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

(8)

• Complexity, combinatorial group theory and the language of palutators
• Relativized alternation and space-bounded computation
• A note on the density of oracle decreasing time-space complexity
• Complexity classes and sparse oracles
• Supportive oracles for parameterized polynomial-time sub-linear-space computations in relation to L, NL, and P
• scientific article; zbMATH DE number 4045155 (Why is no real title available?)
• On quasilinear-time complexity theory
• Simulating time with square-root space

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)