scientific article; zbMATH DE number 4021119

MaRDI QIDQ3764142zbMATHFDO

Authors Thomas Gundermann, Gerd Wechsung

Publication date 1986

zbMATH Keywords

relativizationsBoolean closure of NPhierarchy classesnondeterministic polynomial time Turing machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Recommendations

• Nondeterminism within $P^ * $
• scientific article; zbMATH DE number 176517
• scientific article; zbMATH DE number 3903969
• Improving the classification of complexities
• scientific article; zbMATH DE number 4045156

Cited in

(6)

• The complexity of unions of disjoint sets
• scientific article; zbMATH DE number 3903969 (Why is no real title available?)
• Autoreducibility, mitoticity, and immunity
• Machines that can output empty words
• Languages polylog-time reducible to dot-depth 1/2
• ALTERNATING TURING MACHINES WITH MODIFIED ACCEPTING STRUCTURE

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