scientific article; zbMATH DE number 8798

MaRDI QIDQ3971288zbMATH OpenFDO

Authors Andrzej Szepietowski

Publication date 25 June 1992

zbMATH Keywords

DSPACENSPACEspace complexity

Mathematics Subject Classification ID

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

Recommendations

• If deterministic and nondeterministic space complexities are equal for n then they are also equal for n
• Some notes on strong and weak log log n space complexity
• If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n
• Remarks on languages acceptable in log log n space
• Positive relativizations for log space computability

Cited in

(5)

• Remarks on languages acceptable in log log n space
• Some notes on strong and weak log log n space complexity
• A theory for Log-Space and NLIN versus co-NLIN
• If deterministic and nondeterministic space complexities are equal for n then they are also equal for n
• If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n

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