Genericity and measure for exponential time
From MaRDI portal
Publication:1350990
DOI10.1016/0304-3975(96)89424-2zbMath0874.68094OpenAlexW2070150049MaRDI QIDQ1350990
Sebastiaan A. Terwijn, Hans-Christian Neis, Ambos-Spies, Klaus
Publication date: 27 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: http://dare.uva.nl/personal/pure/en/publications/genericity-and-measure-for-exponential-time(4ffcfdc4-5355-4e0e-91e4-7983d0a34138).html
Related Items
Bounded truth table does not reduce the one-query tautologies to a random oracle ⋮ A thirty year old conjecture about promise problems ⋮ Autoreducibility, mitoticity, and immunity ⋮ Hard sets are hard to find ⋮ Almost complete sets. ⋮ Does truth-table of linear norm reduce the one-query tautologies to a random oracle? ⋮ Generic density and small span theorem ⋮ Special issue: 17th ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, Seattle, WA, USA, June 1--3, 1998 ⋮ Scaled dimension and the Kolmogorov complexity of Turing-hard sets ⋮ Genericity and randomness over feasible probability measures ⋮ Resource-bounded strong dimension versus resource-bounded category ⋮ Resource-bounded martingales and computable Dowd-type generic sets
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- Diagonalizations over polynomial time computable sets
- Almost everywhere high nonuniform complexity
- A comparison of polynomial time reducibilities
- Almost every set in exponential time is P-bi-immune
- 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
- Measure, Stochasticity, and the Density of Hard Languages
- The Complexity and Distribution of Hard Problems
- The definition of random sequences
