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

DOI10.1016/0890-5401(91)90022-TzbMATH Open0722.68056OpenAlexW2045334235MaRDI QIDQ756423FDOQ756423

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

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

zbMATH Keywords

diagonalizationalmost-everywhere-complex setsdeterministic-time-complexity

Mathematics Subject Classification ID

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

Cites Work

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

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
• On genuinely time bounded computations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Towards the Actual Relationship Between NP and Exponential Time
• Almost every set in exponential time is P-bi-immune
• A note on deterministic and nondeterministic time complexity
• Complete distributional problems, hard languages, and resource-bounded measure
• 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)