Weakly complete problems are not rare
From MaRDI portal
Publication:1918951
Recommendations
- Weakly Hard Problems
- Some remarks on weak sufficiency
- Completeness and weak completeness under polynomial-size circuits
- Completeness and weak completeness under polynomial-size circuits
- On quantification of weak sequential completeness
- Weak completeness notions for exponential time
- Weak completeness notions for exponential time
- Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
- scientific article; zbMATH DE number 7695589
Cites work
- A unified approach to the definition of random sequences
- Almost every set in exponential time is P-bi-immune
- Almost everywhere high nonuniform complexity
- An analysis of ML typability
- Category and Measure in Complexity Classes
- Classifying the computational complexity of problems
- scientific article; zbMATH DE number 1335897 (Why is no real title available?)
- scientific article; zbMATH DE number 1555954 (Why is no real title available?)
- Klassifikation der Zufallsgesetze nach Komplexit�t und Ordnung
- Measure, Stochasticity, and the Density of Hard Languages
- Process complexity and effective random tests
- 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
- The Complexity and Distribution of Hard Problems
- The definition of random sequences
Cited in
(8)- Almost complete sets.
- Completeness and weak completeness under polynomial-size circuits
- Weak completeness notions for exponential time
- The Density of Weakly Complete Problems under Adaptive Reductions
- Completeness and weak completeness under polynomial-size circuits
- Equivalence of measures of complexity classes
- A note on measuring in P
- Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
This page was built for publication: Weakly complete problems are not rare
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1918951)
