Almost-everywhere complexity hierarchies for nondeterministic time
The ``almost-everywhere complexity notion differs from the more common ``infinitely-often one in that a set is considered hard if all but a finite number of its elements are hard (as opposite to the existence of just an infinite subset of hard elements). The authors make use of the relation between the almost-everywhere complexity and immunity notions to prove an almost-everywhere complexity hierarchy theorem for nondeterministic time. Moreover they show that their result cannot be improved by using relativizable proof techniques. In addition they consider consistent nondeterministic Turing machines in order to investigate more acceptable notion of almost-everywhere complexity for nondeterministic time and prove a hierarchy theorem for this case as well. Also, in this case their result cannot be improved by relativizable proof techniques.
- scientific article; zbMATH DE number 4205978
- Strong time bounds: Non-computable bounds and a hierarchy theorem
- A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
- A probabilistic-time hierarchy theorem for ``slightly non-uniform algorithms
- Some hierarchies of relativized time-bounded complexity classes
- scientific article; zbMATH DE number 2068877
- A note on deterministic and nondeterministic time complexity
- scientific article; zbMATH DE number 2107051
- Completeness for nondeterministic complexity classes
- Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines
- A hierarchy for nondeterministic time complexity
- A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
- A note on arbitrarily complex recursive functions
- A Turing machine time hierarchy
- Bi-immune sets for complexity classes
- Data structures for distributed counting
- scientific article; zbMATH DE number 4205978 (Why is no real title available?)
- scientific article; zbMATH DE number 4010508 (Why is no real title available?)
- scientific article; zbMATH DE number 4091486 (Why is no real title available?)
- scientific article; zbMATH DE number 88937 (Why is no real title available?)
- scientific article; zbMATH DE number 3586480 (Why is no real title available?)
- scientific article; zbMATH DE number 3407150 (Why is no real title available?)
- Limitations on Separating Nondeterministic Complexity Classes
- On the Computational Complexity of Algorithms
- Separating Nondeterministic Time Complexity Classes
- Strong nondeterministic polynomial-time reducibilities
- Time bounded random access machines
- Time- and tape-bounded Turing acceptors and AFLs
- Two-Tape Simulation of Multitape Turing Machines
- A note on the best-case complexity
- Sharply bounded alternation and quasilinear time
- Almost-everywhere superiority for quantum polynomial time
- Non-recursive trade-offs are ``almost everywhere
- A note on deterministic and nondeterministic time complexity
- scientific article; zbMATH DE number 4205978 (Why is no real title available?)
- scientific article; zbMATH DE number 4010508 (Why is no real title available?)
- scientific article; zbMATH DE number 17551 (Why is no real title available?)
- scientific article; zbMATH DE number 88937 (Why is no real title available?)
- The Descriptive Complexity of the Deterministic Exponential Time Hierarchy
- Time-Complexity Semantics for Feasible Affine Recursions
- Pseudodeterministic algorithms and the structure of probabilistic time
- A note on uniform circuit lower bounds for the counting hierarchy (extended abstract)
- A parameterized halting problem, _0 truth and the MRDP theorem
- A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
- Strong time bounds: Non-computable bounds and a hierarchy theorem
This page was built for publication: Almost-everywhere complexity hierarchies for nondeterministic time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1261465)