Average-case intractability vs. worst-case intractability

DOI10.1016/J.IC.2003.05.002zbMATH Open1085.68057OpenAlexW2000641137MaRDI QIDQ598182FDOQ598182

Authors: Johannes Köbler, Rainer Schuler 

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

Recommendations

• scientific article; zbMATH DE number 1222584
• Fundamentals of Computation Theory
• Relations between average-case and worst-case complexity
• scientific article; zbMATH DE number 5081744
• scientific article; zbMATH DE number 1008518

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• A taxonomy of complexity classes of functions
• The complexity of computing the permanent
• On pseudorandomness and resource-bounded measure
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• Non-deterministic exponential time has two-prover interactive protocols
• Title not available (Why is that?)
• BPP and the polynomial hierarchy
• Oracles and queries that are sufficient for exact learning
• Upper bounds for the complexity of sparse and tally descriptions
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• PP is as Hard as the Polynomial-Time Hierarchy
• Random-Self-Reducibility of Complete Sets
• On the theory of average case complexity
• Average case completeness
• Average Case Complete Problems
• Quantitative Relativizations of Complexity Classes
• Highly resilient correctors for polynomials
• Expected Computation Time for Hamiltonian Path problem
• Complexity and structure
• On hiding information from an oracle
• The power of the middle bit of a \(\#\)P function
• On the power of generalized Mod-classes
• Logarithmic advice classes
• Instance complexity
• Tally languages and complexity classes
• On sparse sets in NP-P
• Computation times of NP sets of different densities
• Robust reductions
• Locating \(P\)/poly optimally in the extended low hierarchy
• 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
• Bounding the complexity of advice functions
• Structural average case complexity
• Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• New Collapse Consequences of NP Having Small Circuits
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (7)

• Collapsing and separating completeness notions under average-case and worst-case hypotheses
• Fundamentals of Computation Theory
• The consequences of eliminating NP solutions
• Relations between average-case and worst-case complexity
• Title not available (Why is that?)
• Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy
• Some Results on Average-Case Hardness Within the Polynomial Hierarchy

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)