Genericity and measure for exponential time
From MaRDI portal
Publication:5096879
DOI10.1007/3-540-58338-6_69zbMath1493.68147OpenAlexW2999683357MaRDI QIDQ5096879
Sebastiaan A. Terwijn, Ambos-Spies, Klaus, Hans-Christian Neis
Publication date: 18 August 2022
Published in: Mathematical Foundations of Computer Science 1994 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-58338-6_69
Related Items (3)
An excursion to the Kolmogorov random strings ⋮ Index sets and presentations of complexity classes ⋮ Resource bounded randomness and weakly complete problems
Cites Work
- Diagonalizations over polynomial time computable sets
- Almost everywhere high nonuniform complexity
- A comparison of polynomial time reducibilities
- Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
- Polynomial-time reducibilities and ``almost all oracle sets
- Category and Measure in Complexity Classes
- Bi-immune sets for complexity classes
- On relativized exponential and probabilistic complexity classes
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- The Complexity and Distribution of Hard Problems
- Almost every set in exponential time is P-bi-immune
- The definition of random sequences
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Genericity and measure for exponential time
