A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes

DOI10.1016/0890-5401(91)90022-TMaRDI QIDQ756423zbMATH OpenOpenAlexFDO

Authors John G. Geske, Dung T. Huynh, Joel I. Seiferas

Publication date 1991

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(91)90022-t

zbMATH Keywords

diagonalizationalmost-everywhere-complex setsdeterministic-time-complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Almost-everywhere complexity hierarchies for nondeterministic time
• Deterministic Turing machines in the range between real-time and linear-time.
• scientific article; zbMATH DE number 88937
• scientific article; zbMATH DE number 17551
• A note on the best-case complexity

Cites work

• scientific article; zbMATH DE number 4010508 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3407150 (Why is no real title available?)
• scientific article; zbMATH DE number 3420624 (Why is no real title available?)
• A Machine-Independent Theory of the Complexity of Recursive Functions
• A Turing machine time hierarchy
• A hierarchy for nondeterministic time complexity
• A note on arbitrarily complex recursive functions
• Bi-immune sets for complexity classes
• Computational Complexity of One-Tape Turing Machine Computations
• Data structures for distributed counting
• Infinite exponent partition relations and well-ordered choice
• Minimizing access pointers into trees and arrays
• On Almost Everywhere Complex Recursive Functions
• On the Computational Complexity of Algorithms
• On time hierarchies
• Separating Nondeterministic Time Complexity Classes
• Simulations among multidimensional Turing machines
• Time bounded random access machines
• Two-Tape Simulation of Multitape Turing Machines

Cited in

(14)

• Almost every set in exponential time is P-bi-immune
• Almost-everywhere superiority for quantum polynomial time
• A note on the best-case complexity
• Reductions and convergence rates of average time
• Dichotomy theorems for families of non-cofinal essential complexity
• scientific article; zbMATH DE number 17551 (Why is no real title available?)
• On genuinely time bounded computations
• scientific article; zbMATH DE number 4205978 (Why is no real title available?)
• Towards the Actual Relationship Between NP and Exponential Time
• Almost every set in exponential time is P-bi-immune
• Complete distributional problems, hard languages, and resource-bounded measure
• A note on deterministic and nondeterministic time complexity
• Almost-everywhere complexity hierarchies for nondeterministic time
• Relations between average-case and worst-case complexity

This page was built for publication: A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q756423)