Average-case intractability vs. worst-case intractability
From MaRDI portal
Publication:598182
DOI10.1016/j.ic.2003.05.002zbMath1085.68057OpenAlexW2000641137MaRDI QIDQ598182
Rainer Schuler, Johannes Köbler
Publication date: 6 August 2004
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: http://nbn-resolving.de/urn:nbn:de:bsz:289-vts-70899
Related Items (2)
The consequences of eliminating NP solutions ⋮ Relations between average-case and worst-case complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Non-deterministic exponential time has two-prover interactive protocols
- Backtrack: An O(1) expected time algorithm for the graph coloring problem
- BPP and the polynomial hierarchy
- Complexity and structure
- Robust reductions
- On sparse sets in NP-P
- Average case completeness
- On the theory of average case complexity
- Logarithmic advice classes
- Highly resilient correctors for polynomials
- On hiding information from an oracle
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- A taxonomy of complexity classes of functions
- Locating \(P\)/poly optimally in the extended low hierarchy
- Computation times of NP sets of different densities
- Some properties of sets tractable under every polynomial-time computable distribution
- New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
- On the NP-isomorphism problem with respect to random instances
- The power of the middle bit of a \(\#\)P function
- Bounding the complexity of advice functions
- Structural average case complexity
- Oracles and queries that are sufficient for exact learning
- Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
- Random-Self-Reducibility of Complete Sets
- PP is as Hard as the Polynomial-Time Hierarchy
- Average Case Complete Problems
- Quantitative Relativizations of Complexity Classes
- Expected Computation Time for Hamiltonian Path problem
- New Collapse Consequences of NP Having Small Circuits
- Instance complexity
- Tally languages and complexity classes
- On the power of generalized Mod-classes
- Upper bounds for the complexity of sparse and tally descriptions
- On pseudorandomness and resource-bounded measure
This page was built for publication: Average-case intractability vs. worst-case intractability
