Some properties of sets tractable under every polynomial-time computable distribution

DOI10.1016/0020-0190(95)00108-OzbMath0875.68537MaRDI QIDQ1350351

Rainer Schuler

Publication date: 27 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

Computational complexityAverage-case analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Average-case intractability vs. worst-case intractability ⋮ Polynomial time samplable distributions

Cites Work

• Unnamed Item
• A Turing machine time hierarchy
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• Computational complexity of real functions
• Average case completeness
• On the theory of average case complexity
• On the greedy algorithm for satisfiability
• Average case complexity under the universal distribution equals worst- case complexity
• Average Case Complete Problems
• Expected Computation Time for Hamiltonian Path problem
• The Complexity of Malign Measures
• The NP-completeness column: An ongoing guide