Complete distributional problems, hard languages, and resource-bounded measure
From MaRDI portal
(Redirected from Publication:1575682)
Recommendations
Cites work
- scientific article; zbMATH DE number 1263208 (Why is no real title available?)
- scientific article; zbMATH DE number 1072536 (Why is no real title available?)
- scientific article; zbMATH DE number 1072538 (Why is no real title available?)
- A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
- Almost every set in exponential time is P-bi-immune
- Almost everywhere high nonuniform complexity
- Average Case Complete Problems
- Average case completeness
- Bi-immune sets for complexity classes
- Computation times of NP sets of different densities
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- Fine Separation of Average-Time Complexity Classes
- Matrix Transformation Is Complete for the Average Case
- On the Computational Complexity of Algorithms
- On the NP-isomorphism problem with respect to random instances
- On the definitions of some complexity classes of real numbers
- On the theory of average case complexity
- P-Printable Sets
- Reductions do not preserve fast convergence rates in average time
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
Cited in
(3)
This page was built for publication: Complete distributional problems, hard languages, and resource-bounded measure
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1575682)
