scientific article; zbMATH DE number 4045155

MaRDI QIDQ3782783zbMATH OpenFDO

Authors Giancarlo Mauri, Alberto Bertoni, N. Sabadini

Publication date 1987

zbMATH Keywords

nondeterministic oracle Turing machinesrandom oracle

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• An NL hierarchy
• RelativizedNC
• scientific article; zbMATH DE number 3992933
• Positive relativizations for log space computability
• On relativized exponential and probabilistic complexity classes

Cited in

(5)

• Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n) NSPACE( \,n)
• An NL hierarchy
• Supportive oracles for parameterized polynomial-time sub-linear-space computations in relation to L, NL, and P
• Positive relativizations for log space computability
• Finite state verifiers with constant randomness

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