scientific article; zbMATH DE number 1222596

MaRDI QIDQ4218136zbMATH OpenFDO

Authors Jiří Wiedermann

Publication date 2 March 1999

zbMATH Keywords

complexity classesnondeterministic Turing machineseparationspeed-up

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 2102763
• scientific article; zbMATH DE number 5593330
• Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones
• Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time
• scientific article; zbMATH DE number 3984575
• On the complexity of 1-tape ATMs and off-line 1-tape ATMs running in constant reversals
• scientific article; zbMATH DE number 88942
• Speed-Up of Turing Machines with One Work Tape and a Two-Way Input Tape
• The speed of copying on one-tape off-line turing machines

Cited in

(6)

• scientific article; zbMATH DE number 4213433 (Why is no real title available?)
• Alternating time versus deterministic time: A separation
• scientific article; zbMATH DE number 2102763 (Why is no real title available?)
• scientific article; zbMATH DE number 5593330 (Why is no real title available?)
• Complexity of nondeterministic multitape computations based on crossing sequences
• Separation of deterministic, nondeterministic and alternating 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 Q4218136)