Genericity and measure for exponential time

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

Mathematics Subject Classification ID

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

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