scientific article; zbMATH DE number 3926244

MaRDI QIDQ3700835zbMATH OpenFDO

Authors Gerhard Lischke

Publication date 1986

zbMATH Keywords

computational complexity classesexponential timepolynomial timequery machinesrecursive oracles

Mathematics Subject Classification ID

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

Recommendations

• On relativized exponential and probabilistic complexity classes
• Relativizations comparing NP and exponential time
• scientific article; zbMATH DE number 4011940
• Oracles for Deterministic Versus Alternating Classes
• Towards the Actual Relationship Between NP and Exponential Time

Cited in

(5)

• A general method to construct oracles realizing given relationships between complexity classes
• On Relativized Polynomial and Exponential Computations
• Oracle‐Constructions to Prove All Possible Relationships Between Relativizations of P, NP, EL, NEL, EP and NEP
• On relativized exponential and probabilistic complexity classes
• Two oracles that force a big crunch

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