Weakly complete problems are not rare
From MaRDI portal
Publication:1918951
DOI10.1007/BF01206322zbMath0849.03026MaRDI QIDQ1918951
Publication date: 4 November 1996
Published in: Computational Complexity (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Equivalence of measures of complexity classes, A note on measuring in P, Almost complete sets., Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
Cites Work
- Almost everywhere high nonuniform complexity
- Almost every set in exponential time is P-bi-immune
- Process complexity and effective random tests
- Category and Measure in Complexity Classes
- Classifying the computational complexity of problems
- Provably Difficult Combinatorial Games
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- An analysis of ML typability
- Measure, Stochasticity, and the Density of Hard Languages
- The Complexity and Distribution of Hard Problems
- [https://portal.mardi4nfdi.de/wiki/Publication:5587565 Klassifikation der Zufallsgesetze nach Komplexit�t und Ordnung]
- A unified approach to the definition of random sequences
- The definition of random sequences
- Unnamed Item
- Unnamed Item
