Average-case intractability vs. worst-case intractability
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 4213418 (Why is no real title available?)
- scientific article; zbMATH DE number 48150 (Why is no real title available?)
- scientific article; zbMATH DE number 3485216 (Why is no real title available?)
- scientific article; zbMATH DE number 1263208 (Why is no real title available?)
- scientific article; zbMATH DE number 1304313 (Why is no real title available?)
- scientific article; zbMATH DE number 512798 (Why is no real title available?)
- scientific article; zbMATH DE number 549854 (Why is no real title available?)
- scientific article; zbMATH DE number 719756 (Why is no real title available?)
- scientific article; zbMATH DE number 1962815 (Why is no real title available?)
- A taxonomy of complexity classes of functions
- Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
- Average Case Complete Problems
- Average case completeness
- BPP and the polynomial hierarchy
- Backtrack: An O(1) expected time algorithm for the graph coloring problem
- Bounding the complexity of advice functions
- Complexity and structure
- Computation times of NP sets of different densities
- Expected Computation Time for Hamiltonian Path problem
- Highly resilient correctors for polynomials
- Instance complexity
- Locating \(P\)/poly optimally in the extended low hierarchy
- Logarithmic advice classes
- New Collapse Consequences of NP Having Small Circuits
- New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
- Non-deterministic exponential time has two-prover interactive protocols
- On hiding information from an oracle
- On pseudorandomness and resource-bounded measure
- On sparse sets in NP-P
- On the NP-isomorphism problem with respect to random instances
- On the power of generalized Mod-classes
- On the theory of average case complexity
- Oracles and queries that are sufficient for exact learning
- PP is as Hard as the Polynomial-Time Hierarchy
- Quantitative Relativizations of Complexity Classes
- Random-Self-Reducibility of Complete Sets
- Robust reductions
- Some properties of sets tractable under every polynomial-time computable distribution
- Structural average case complexity
- Tally languages and complexity classes
- The complexity of computing the permanent
- The power of the middle bit of a \(\#\)P function
- Upper bounds for the complexity of sparse and tally descriptions
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
Cited in
(7)- Fundamentals of Computation Theory
- Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy
- scientific article; zbMATH DE number 1180007 (Why is no real title available?)
- Some Results on Average-Case Hardness Within the Polynomial Hierarchy
- Collapsing and separating completeness notions under average-case and worst-case hypotheses
- The consequences of eliminating NP solutions
- Relations between average-case and worst-case complexity
This page was built for publication: Average-case intractability vs. worst-case intractability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q598182)
