Almost every set in exponential time is P-bi-immune

DOI10.1016/0304-3975(94)00023-CzbMath0874.68161WikidataQ60578990 ScholiaQ60578990MaRDI QIDQ1349712

Elvira Mayordomo

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Equivalence of measures of complexity classes, Genericity and measure for exponential time, On resource-bounded instance complexity, ON OPTIMAL INVERTERS, A note on measuring in P, The size of SPP, Results on resource-bounded measure, Weakly complete problems are not rare, A new algorithm design technique for hard problems, A zero-one SUBEXP-dimension law for BPP, Non-uniform reductions, Hard sets are hard to find, Almost complete sets., Martingale families and dimension in P, Cook versus Karp-Levin: Separating completeness notions if NP is not small, Effective category and measure in abstract complexity theory, Upward separations and weaker hypotheses in resource-bounded measure, Effective category and measure in abstract complexity theory, A Logic for PTIME and a Parameterized Halting Problem, On the complexity of Gödel's proof predicate, Quantitative aspects of speed-up and gap phenomena, Hard Instances of Algorithms and Proof Systems, On the size of classes with weak membership properties, Resource bounded randomness and computational complexity, Complete distributional problems, hard languages, and resource-bounded measure, Genericity, Randomness, and Polynomial-Time Approximations, Resource-bounded strong dimension versus resource-bounded category

Cites Work

• A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
• Diagonalizations over polynomial time computable sets
• Almost everywhere high nonuniform complexity
• On 1-truth-table-hard languages
• Category and Measure in Complexity Classes
• Relativizations comparing NP and exponential time
• Bi-immune sets for complexity classes
• Provably Difficult Combinatorial Games
• Completeness, Approximation and Density
• On Reducibility to Complex or Sparse Sets
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Recursively enumerable sets of positive integers and their decision problems
• Unnamed Item
• Unnamed Item
• Unnamed Item