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

DOI10.1016/0020-0190(95)00108-OMaRDI QIDQ1350351zbMATH OpenFDO

Authors 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)

Recommendations

• On the theory of average case complexity
• scientific article; zbMATH DE number 512799
• scientific article; zbMATH DE number 512870

Cites work

• scientific article; zbMATH DE number 512799 (Why is no real title available?)
• A Turing machine time hierarchy
• Average Case Complete Problems
• Average case completeness
• Average case complexity under the universal distribution equals worst- case complexity
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• Computational complexity of real functions
• Expected Computation Time for Hamiltonian Path problem
• On the greedy algorithm for satisfiability
• On the theory of average case complexity
• The Complexity of Malign Measures
• The NP-completeness column: An ongoing guide

Cited in

(5)

• Structure in average case complexity
• Average-case intractability vs. worst-case intractability
• Average polynomial time is hard for exponential time under sn-reductions
• Sets computable in polynomial time on average
• Polynomial time samplable distributions

This page was built for publication: Some properties of sets tractable under every polynomial-time computable distribution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1350351)