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

DOI10.1007/3-540-55808-X_38zbMath1493.68152MaRDI QIDQ5096852

Elvira Mayordomo

Publication date: 18 August 2022

Published in: Mathematical Foundations of Computer Science 1992 (Search for Journal in Brave)

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Sets computable in polynomial time on average ⋮ On the topological size of p-m-complete degrees ⋮ Genericity and measure for exponential time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
• Oracle-dependent properties of the lattice of NP sets
• Almost everywhere high nonuniform complexity
• On 1-truth-table-hard languages
• Immunity, Relativizations, and Nondeterminism
• Category and Measure in Complexity Classes
• Relativizations comparing NP and exponential time
• Simplicity, Relativizations and Nondeterminism
• Bi-immune sets for complexity classes
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Completeness, Approximation and Density
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• The Complexity and Distribution of Hard Problems
• Recursively enumerable sets of positive integers and their decision problems