scientific article; zbMATH DE number 3926243

MaRDI QIDQ3700834zbMATH OpenFDO

Authors Gerhard Lischke

Publication date 1987

zbMATH Keywords

computational complexity classesexponential timenondeterministic polynomial timesparse sets

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4068281
• scientific article; zbMATH DE number 4080914
• Towards the Actual Relationship Between NP and Exponential Time
• scientific article; zbMATH DE number 4011940
• Sparse Sets in : Relativizations

Cited in

(10)

• Relativized separation of EQP from \(\text{P}^{\text{NP}}\)
• Shellings from relative shellings, with an application to NP-completeness
• NE is not NP Turing reducible to nonexponentially dense NP sets
• Limitations of the upward separation technique
• Oracle‐Constructions to Prove All Possible Relationships Between Relativizations of P, NP, EL, NEL, EP and NEP
• scientific article; zbMATH DE number 4068281 (Why is no real title available?)
• scientific article; zbMATH DE number 4080914 (Why is no real title available?)
• Towards the Actual Relationship Between NP and Exponential Time
• Separating NE from Some Nonuniform Nondeterministic Complexity Classes
• Separating NE from some nonuniform nondeterministic 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 Q3700834)