scientific article; zbMATH DE number 88937

MaRDI QIDQ4016514zbMATH OpenFDO

Authors John G. Geske, Diane Kakihara

Publication date 16 January 1993

zbMATH Keywords

almost-everywhere complex functionsalmost-everywhere complex setsbi-immune setsnondeterministic complexity classesnondeterministic spacestrong separation theorem

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Almost-everywhere complexity hierarchies for nondeterministic time
• scientific article; zbMATH DE number 4010508
• Bi-immune sets for complexity classes
• Almost everywhere high nonuniform complexity
• Almost every set in exponential time is P-bi-immune

Cited in

(8)

• A note on the best-case complexity
• Almost-everywhere complexity hierarchies for nondeterministic time
• Almost every set in exponential time is P-bi-immune
• Bi-immunity over different size alphabets
• Bi-immune sets for complexity classes
• A note on balanced immunity
• Almost every set in exponential time is P-bi-immune
• A note on almost-everywhere-complex sets and separating deterministic- time-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 Q4016514)